Difference between revisions of "User:Richard Pinch/sandbox-12"
(→Singleton bound: more, cite Macwilliams & Sloane (1985)) |
(move text) |
||
Line 127: | Line 127: | ||
* F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes. Parts I, II" (3rd repr.) North-Holland Mathematical Library '''16''' Elsevier (1985) ISBN 0-444-85193-3 {{ZBL|0657.94010}} | * F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes. Parts I, II" (3rd repr.) North-Holland Mathematical Library '''16''' Elsevier (1985) ISBN 0-444-85193-3 {{ZBL|0657.94010}} | ||
* H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 {{ZBL|0816.14011}} | * H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 {{ZBL|0816.14011}} | ||
+ | |||
+ | =BCH code= | ||
+ | A [[cyclic code]] over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$. | ||
+ | |||
+ | The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the ''BCH bound''. | ||
+ | |||
+ | As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code. | ||
+ | |||
+ | ====References==== | ||
+ | * C.M. Goldie, R.G.E. Pinch, ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) ISBN 0-521-40456-8 {{ZBL|0746.94001}} |
Revision as of 19:18, 29 January 2018
Dyck path
A lattice path on the square lattice from the origin $(0,0)$ to some point $(n,n)$ consisting of $2n$ steps of the form $N : (x,y) \rightarrow (x,y+1)$ and $E : (x,y) \rightarrow (x+1,y)$ with the property that the path never passes below the line $y=x$.
The number of Dyck paths of length $2n$ is given by the $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$
References
Catalan number
The $n$-th Catalan number $$ C_n = \frac{1}{n+1}\binom{2n}{n} \ . $$ The generating function is given by $$ \sum_{n=1}^\infty C_n z^n = \frac{1-\sqrt{1-4z}}{2z} \ . $$ The Catalan numbers appear in the enumeration of a number of combinatorially defined object:
- Bernoulli excursion
- Dyck paths
- Parenthesised sequences; words of the Dyck language
- Complete binary rooted plane trees
References
Poisson ratio
The ratio of longitudinal extension to lateral compression when an elastic substance is put under tension.
See: Elasticity, mathematical theory of; Lamé constants.
References
- Horace Lamb, "Statics", Cambridge University Press (1960)
Elastic modulus
Young's modulus
The ratio of longitudinal extension to force applied per unit area when an elastic substance is put under tension.
See: Elasticity, mathematical theory of; Lamé constants.
References
- Horace Lamb, "Statics", Cambridge University Press (1960)
Partition symbol
A notation used to compactly express propositions of partition calculus. The symbol $$ \alpha \rightarrow (\beta)_\gamma^r $$ for cardinals $\alpha,\beta,\gamma$ and natural number $r$, denotes the following proposition.
Given a set $S$ and a colouring of $S^r$ into a set of $\gamma$ colours, there exists a subset $T$ of $S$ of cardinality $|T|=\beta$ such that the colouring restricted to $T^r$ is monochrome.
Here a colouring of a set $X$ by a set of colours $C$ is simply a partition of $X$ into parts indexed by the set $C$.
The symbol $$ \alpha \rightarrow (\beta_1,\ldots,\beta_j)^r $$ denotes the following proposition:
Given a set $S$ of cardinality $\alpha$ and a colouring of $S^r$ by $j$ colours, there exists an index $i$ subset $T$ of $S$ of cardinality $|T|=\beta_i$ such that the colouring restricted to $T^r$ is monochrome.
Examples.
- Ramsey's theorem: $\omega \rightarrow (\omega)_n^r$.
- Sierpinski's theorem: $c \not\rightarrow (\omega_1,\omega_2)^2$.
References
- M.E. Rudin, "Lectures on set theoretic topology", Amer. Math. Soc. (1975) ISBN 0-8218-1673-X Zbl 0318.54001
Isthmus
bridge, co-loop
An isthmus of a graph is an edge for which deletion increases the number of connected components of the graph.
An isthmus of a matroid $M$ on a set $E$ is an element of $E$ which is in every basis for $M$. An element of $E$ is a co-loop of $M$ if and only if it is a loop of the dual matroid $M^*$, that is, does not belong to any base of $M^*$. If $M$ is a graphic matroid, then the definitions coincide.
References
- J. G. Oxley, "Matroid Theory" (2 ed) Oxford University Press (2011) ISBN 978-0-19-856694-6 Zbl 1254.05002
- D. J. A. Welsh, "Matroid Theory", Dover (2010) [1976] ISBN 0486474399 0343.05002
Ordered topological space
A topological space $X$ with a partial order ${\le}$ related to the topology by the condition that if $x < y$ then there are neighbourhoods $N_x$, $N_y$ such that $x < y'$ for all $y' \in N_y$ and $x' < y$ for all $x' \in N_x$. An ordered topological space is necessarily a Hausdorff space.
An ordered topological space is totally order-disconnected if whenever $x \not\le y$ there exists a clopen down-set $D$ such that $x \not\in D$ and $y \in D$.
A Priestley space is a compact totally order-disconnected space. An Ockham space is a Priestley space equipped with an order-reversing continuous mapping $g$: see also Ockham algebra.
References
- Samuel Eilenberg, "Ordered Topological Spaces", American Journal of Mathematics 63 (1941) 39-45 DOI 10.2307/2371274 Zbl 0024.19203
- T.S. Blyth, "Lattices and ordered algebraic structures", Springer (2005) ISBN 1-85233-905-5 Zbl 1073.06001
Reed–Solomon code
A family of codes defined over finite fields. Let $k = \mathbf{F}_q$ and put $n = q-1$. Let $\beta$ be a primitive element of $k^*$. For an integer $k \le n$, let $L_q$ denote the vector space of polynomials over $k$ of degree $\le k-1$, and let $E$ be the evaluation map $e : L_k \rightarrow k^n$ given by $$ E : f \mapsto \left({ f(\beta), f(\beta^2), \ldots, f(\beta^n) }\right) \ . $$
The image $E[L_k]$ is a subspace of $k^n$ and is the Reed–Solomon code $\mathrm{RS}(q,k)$.
The map $E$ is injective, as a non-zero polynomial of degree $k<n$ cannot be zero at $n$ distinct values. The rank of the code is thus $k$. The minimum weight is $n-k+1$, corresponding to a polynomial with $k-1$ zeroes all in $k$. The Reed–Solomon code thus meets the singleton bound and is an MDS code.
References
- C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
- J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
- H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011
Singleton bound
A constraint on the parameters of a linear block code. If a code has length $n$, rank $k$ and minimum distance $d$, then $$ k+d \le n+1 \ . $$ The bound is obtained by puncturing a code $C$ by selecting all the words with the symbol $0$ in a specific location and then deleting that symbol from all words.
A code for which equality holds is a maximum distance separable or MDS code. Examples of MDS codes are the Reed–Solomon codes, which show that if $n \le q+1$ there are MDS codes over $\mathbf{F}_q$ of rank $k$ for all $k< n$.
References
- C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
- J.H. van Lint, "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
- F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes. Parts I, II" (3rd repr.) North-Holland Mathematical Library 16 Elsevier (1985) ISBN 0-444-85193-3 Zbl 0657.94010
- H. Stichtenoth, "Algebraic function fields and codes", Universitext, Springer (1993) ISBN 3-540-58469-6 Zbl 0816.14011
BCH code
A cyclic code over a finite field. Fix length $n$ and ground field $\mathbf{F}_q$ and a design distance parameter $\delta$. Let $\beta$ be a primitive $n$-th root of unity in a suitable extension of $\mathbf{F}_q$. The generator of the cyclic code is the least common multiple $g$ of the minimal polynomials (over $\mathbf{F}_q$) of the elements $\beta^1, \beta^2, \ldots, \beta^{\delta-1}$.
The minimum distance of the BCH code generated by $g$ is at least $\delta$: this is the BCH bound.
As an example, let $q=2$ and $\beta$ be a primitive $7$-th root of unity in $\mathrm{F}_{8}$: we may take $\beta$ to satisfy the polynomial $x^3 + x + 1$. Choose $\delta = 3$. The minimal polynomial for $\beta^2$ is the same as that of $\beta$, so that the cyclic code is generated by the word $1101000$. This is in fact the Hamming [7,4] code.
References
- C.M. Goldie, R.G.E. Pinch, Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
Richard Pinch/sandbox-12. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-12&oldid=42802