formulasearchengine - User contributions [en]

Hamming bound

2014-01-10T00:21:43Z

91.85.75.177: /* Background on error-correcting codes */ bad grammar.

{{Refimprove|date=December 2009}}
In [[coding theory]], the '''Gilbert–Varshamov bound''' (due to [[Edgar Gilbert]]<ref>{{citation|first=E. N.|last=Gilbert|authorlink=Edgar Gilbert|title=A comparison of signalling alphabets|journal=[[Bell System Technical Journal]]|volume=31|year=1952|pages=504–522}}.</ref> and independently Rom Varshamov<ref>{{citation|first=R. R.|last=Varshamov|title=Estimate of the number of signals in error correcting codes|journal=Dokl. Acad. Nauk SSSR|volume=117|year=1957|pages=739–741}}.</ref>) is a limit on the parameters of a (not necessarily [[linear code|linear]]) [[code]]. It is occasionally known as the '''Gilbert–[[Claude Shannon|Shannon]]–Varshamov bound''' (or the '''GSV bound'''), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear code. For more about that proof, see: [[GV-linear-code]].

==Statement of the bound==
Let

:<math>A_q(n,d)</math>

denote the maximum possible size of a ''q''-ary code <math>C</math> with length ''n'' and minimum [[Hamming weight]] ''d'' (a ''q''-ary code is a code over the [[field (mathematics)|field]] <math>\mathbb{F}_q</math> of ''q'' elements).

Then:

:<math>A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j}.</math>

==Proof==
Let <math>C</math> be a code of length <math>n</math> and minimum [[Hamming distance]] <math>d</math> having maximal size:

:<math>|C|=A_q(n,d).\,</math>

Then for all <math>x\in\mathbb{F}_q^n</math> , there exists at least one codeword <math>c_x \in C</math> such that the Hamming distance <math>d(x,c_x)</math> between <math>x</math> and <math>c_x</math> satisfies

:<math>d(x,c_x)\leq d-1</math>

since otherwise we could add ''x'' to the code whilst maintaining the code's minimum Hamming distance ''d'' – a contradiction on the maximality of <math>|C|</math>.

Hence the whole of <math>\mathbb{F}_q^n</math> is contained in the [[union (set theory)|union]] of all [[ball (mathematics)|balls]] of radius ''d'' − 1 having their [[ball (mathematics)|centre]] at some <math>c \in C</math> :

:<math>\mathbb{F}_q^n =\cup_{c \in C} B(c,d-1).\, </math>

Now each ball has size

:<math>
\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j
</math>

since we may allow (or [[binomial coefficients|choose]]) up to <math>d-1</math> of the <math>n</math> components of a codeword to deviate (from the value of the corresponding component of the ball's [[ball (mathematics)|centre]]) to one of <math>(q-1)</math> possible other values (recall: the code is q-ary: it takes values in <math>\mathbb{F}_q^n</math>). Hence we deduce

:<math>
\begin{align}
|\mathbb{F}_q^n| & = |\cup_{c \in C} B(c,d-1)| \\
\\
& \leq \sum_{c \in C} |B(c,d-1)| \\
\\
& = |C|\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j \\
\\
\end{align}
</math>

That is:

:<math>
A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j}
</math>

(using the fact: <math>|\mathbb{F}_q^n|=q^n</math>).

==An improvement in the prime power case==
For ''q'' a prime power, one can improve the bound to <math>A_q(n,d)\ge q^k</math> where ''k'' is the greatest integer for which

: <math>q^k < \frac{q^n}{\sum_{j=0}^{d-2} \binom{n-1}{j}(q-1)^j}.</math>

==See also==
*[[Singleton bound]]
*[[Hamming bound]]
*[[Johnson bound]]
*[[Plotkin bound]]
*[[Griesmer bound]]
*[[Grey–Rankin bound]]
*[[GV-linear-code|Gilbert–Varshamov bound for linear code]]
*[[Elias-Bassalygo bound]]

==References==

{{Reflist}}

{{DEFAULTSORT:Gilbert-Varshamov Bound}}
[[Category:Coding theory]]
[[Category:Articles containing proofs]]

Representativeness heuristic

2014-01-07T15:25:19Z

91.85.41.151:

{{Infobox Polygon
| name = Isosceles trapezoid
| image = Isosceles trapezoid.svg
| caption = Isosceles trapezoid with axis of symmetry
| type = [[quadrilateral]], [[trapezoid]]
| edges = 4
| symmetry = [[Dihedral symmetry|Dih2]], [ ], (*), order 2
| schläfli =
| wythoff =
| coxeter =
| area =
| dual = [[Kite (geometry)|Kite]]
| properties = [[convex polygon|convex]], [[Cyclic polygon|cyclic]]
}}

In [[Euclidean geometry]], an '''isosceles trapezoid''' ('''isosceles trapezium''' in [[British English]]) is a [[convex polygon|convex]] [[quadrilateral]] with a line of [[symmetry]] bisecting one pair of opposite sides, making it automatically a [[trapezoid]]. Some sources would qualify this with the exception: "excluding rectangles." Two opposite sides (the bases) are [[Parallel (geometry)|parallel]], and the two other sides (the legs) are of equal length (a property shared by the isosceles trapezoid and by the [[parallelogram]]). The diagonals are also of equal length. The base angles of an isosceles trapezoid are equal in measure (there are in fact two pairs of equal base angles, where one base angle is the [[supplementary angle]] of a base angle at the other base).

Any non-self-crossing quadrilateral with exactly one axis of symmetry must be either an isosceles trapezoid or a [[kite (geometry)|kite]].<ref name="esg"/> However, if crossings are allowed, the set of symmetric quadrilaterals must be expanded to include also the [[antiparallelogram]]s, crossed quadrilaterals in which opposite sides have equal length. Every antiparallelogram has an isosceles trapezoid as its convex hull, and may be formed from the diagonals and non-parallel sides of an isosceles trapezoid.<ref>{{citation |title=The Century Dictionary and Cyclopedia |first1=William Dwight |last1=Whitney |first2= Benjamin Eli |last2=Smith |publisher=The Century co. |year=1911 |url=http://books.google.com/books?id=ownpAAAAMAAJ&pg=PA1547 |page=1547}}.</ref>
The isosceles trapezoid is also (rarely) known as a '''symtra''' because of its symmetry.<ref name="esg">{{citation |title=Elementary Synthetic Geometry |first=George Bruce |last=Halsted |publisher=J. Wiley & sons |year=1896 |contribution=Chapter XIV. Symmetrical Quadrilaterals |url=http://books.google.com/books?id=H3ALAAAAYAAJ&pg=PA49 |pages=49–53 |authorlink=G. B. Halsted}}.</ref>

==Special cases==
Examples of isosceles trapezoids (under the [[Trapezoids#Definition|inclusive definition]] of trapezoids) are [[rectangle]]s and [[Square (geometry)|square]]s.

==Characterizations==
If a quadrilateral is known to be a [[trapezoid]], it is not necessary to check that the legs have the same length in order to know that it is an isosceles trapezoid; any of the following properties also distinguishes an isosceles trapezoid from other trapezoids:
*The diagonals have the same length.
*The base angles have the same measure.
*An isosceles triangle is formed by the base and the extensions of the legs. (Rectangles are excluded here.)
*The segment that joins the midpoints of the parallel sides is perpendicular to them.
*Opposite angles are supplementary, which in turn implies that isosceles trapezoids are [[cyclic quadrilateral]]s.
*The diagonals divide each other into segments with lengths that are pairwise equal; in terms of the picture below, {{nowrap|''AE'' {{=}} ''DE''}}, {{nowrap|''BE'' {{=}} ''CE''}} (and {{nowrap|''AE'' ≠ ''CE''}} if one wishes to exclude rectangles).

If rectangles are included in the class of trapezoids then one may concisely define an isosceles trapezoid as "a cyclic quadrilateral with equal diagonals"<ref>[http://mzone.mweb.co.za/residents/profmd/classify.pdf Mzone.mweb.co.za]</ref> or as "a cyclic quadrilateral with a pair of parallel sides."

==Angles==
In an isosceles trapezoid the base angles have the same measure pairwise. In the picture below, angles ∠''ABC'' and ∠''DCB'' are [[Angle#Types of angles|obtuse]] angles of the same measure, while angles ∠''BAD'' and ∠''CDA'' are [[Angle#Types of angles|acute angle]]s, also of the same measure.

Since the lines ''AD'' and ''BC'' are parallel, angles adjacent to opposite bases are [[Supplementary angles|supplementary]], that is, angles {{nowrap|&ang;''ABC'' + &ang;''BAD'' {{=}} 180°.}}

==Diagonals and height==
[[Image:Isoscelestriangle2.svg|thumb|350px|right|Another isosceles trapezoid.]]
The [[diagonal]]s of an isosceles trapezoid have the same length; that is, every isosceles trapezoid is an [[equidiagonal quadrilateral]]. Moreover, the diagonals divide each other in the same proportions. As pictured, the diagonals ''AC'' and ''BD'' have the same length ({{nowrap|''AC'' {{=}} ''BD''}}) and divide each other into segments of the same length ({{nowrap|''AE'' {{=}} ''DE''}} and {{nowrap|''BE'' {{=}} ''CE''}}).

The [[ratio]] in which each diagonal is divided is equal to the ratio of the lengths of the parallel sides that they intersect, that is,
:<math>\frac{AE}{EC} = \frac{DE}{EB} = \frac{AD}{BC}.</math>

The length of each diagonal is, according to [[Ptolemy's theorem]], given by
:<math>p=\sqrt{ab+c^2}</math>

where ''a'' and ''b'' are the lengths of the parallel sides ''AD'' and ''BC'', and ''c'' is the length of each leg ''AB'' and ''CD''.

The height is, according to the [[Pythagorean theorem]], given by
:<math>h=\sqrt{p^2-\left(\frac{a+b}{2}\right)^2}=\tfrac{1}{2}\sqrt{4c^2-(a-b)^2}.</math>

The distance from point ''E'' to base ''AD'' is given by
:<math>d=\frac{ah}{a+b}</math>
where ''a'' and ''b'' are the lengths of the parallel sides ''AD'' and ''BC'', and ''h'' is the height of the trapezoid.

==Area==
The area of an isosceles (or any) trapezoid is equal to the average of the lengths of the base and top (''the parallel sides'') times the height. In the diagram to the right, if we write {{nowrap|''AD'' {{=}} ''a''}}, and {{nowrap|''BC'' {{=}} ''b''}}, and the height ''h'' is the length of a line segment between ''AD'' and ''BC'' that is perpendicular to them, then the area ''K'' is given as follows:
:<math>K=\frac{h\left(a+b\right)}{2}.</math>

If instead of the height of the trapezoid, the length of the leg ''AB'' = ''c'' is known, then the area can be computed using the formula
:<math>K = \sqrt{(s-a)(s-b)(s-c)^2}</math>,

where <math>s = \tfrac{1}{2}(a + b + 2c)</math> is the semiperimeter of the trapezoid. This formula is analogous to [[Heron's formula]] to compute the area of a triangle. The previous formula for area can also be written as
:<math>K= \sqrt{\frac{(a+b)^2(a-b+2c)(b-a+2c)}{16}}.</math>

==Circumradius==
The radius in the circumcribed circle is given by
:<math>R=c\sqrt{\frac{ab+c^2}{4c^2-(a-b)^2}}.</math>

In a [[rectangle]] where ''a'' = ''b'' this is simplified to <math>R=\tfrac{1}{2}\sqrt{a^2+c^2}</math>.

==See also==

*[[Tangential trapezoid#Isosceles tangential trapezoid|Isosceles tangential trapezoid]]

== References ==
{{reflist}}

==External links==
*[http://www.efunda.com/math/areas/IsosTrapazoid.cfm Some engineering formulas involving isosceles trapezoids]

[[Category:Quadrilaterals]]
[[Category:Polygons]]

[[bg:Трапец]]
[[pl:Trapez równoramienny]]

Seymour Narrows

2012-01-14T22:28:47Z

91.85.51.38:

Hi there. My title is Sophia Meagher although it is not the name on my beginning certificate. Mississippi is where his house is. Credit authorising is how she makes a living. As a lady what she truly likes is fashion and she's been doing it for fairly a while. My website :: free tarot readings ([http://165.132.39.93/xe/visitors/372912 165.132.39.93])