In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, Reed–Muller codes and Polar codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using Boolean polynomials.
Algebraic block codes are typically hard-decoded using algebraic decoders.n bits of output data C:Σk→Σn.
Here, n are integers. The meaning and significance of these three parameters and other parameters related to the code are described below.
The alphabet Σ
editThe data stream to be encoded is modeled as a string over some alphabet q. If Σ with the finite field Σk, that is, strings of length n of a block code is the number of symbols in a block. Hence, the elements n and correspond to blocks that may be received by the receiver. Hence they are also called received words. If c is called the codeword of 1−R measures the overhead that occurs due to the encoding with the block code. It is a simple information theoretical fact that the rate cannot exceed δ is the fraction Δ(c1,c2) denote the Hamming distance between c1 and C is defined as
-
- d−1 transmission errors since changing (d−1)/2. If more than Σ of size k, and distance q=2, the index is sometimes dropped.
For maximum distance separable codes, the distance is always (n,M,d)q is used for codes that contain k over an alphabet of size [7,4,3]2 code.
Reed–Solomon codes are a family of q being a prime power. Rank codes are family of [n,k,d]2 codes with c∈Σncould be considered as a point in the 𝒞 is the subset of d means that d−1, which is defined as the collection of d−1. Similarly, 𝒞 can detect d−1, no error pattern of 𝒞 can correct d−1, the two Hamming balls centered at two different codewords respectively with both radius ⌊d−12⌋, there is only one codeword in the hamming ball centered at (d−1)/2 errors, list-decoding or maximum likelihood decoding can be used.
- q-passing decoding : In ⌊d−12⌋ and therefore the erasures could be corrected.
Lower and upper bounds of block codes
edit
Hamming limit- light orange on x axis: trivial unprotected codes
- orange on y axis: trivial repeat codes
- dark orange on data set d=3: classic perfect Hamming codes
- dark red and larger: the only perfect binary Golay code
- d−1 transmission errors since changing (d−1)/2. If more than Σ of size k, and distance q=2, the index is sometimes dropped.
For maximum distance separable codes, the distance is always (n,M,d)q is used for codes that contain k over an alphabet of size [7,4,3]2 code.
Family of codes
edit(ni,ki,di)q code with monotonic increasing R(C)=limi→∞kini
Relative distance of family of codes R(C) and k+d≤n+1. Reed–Solomon codes are non-trivial examples of codes that satisfy the singleton bound with equality.
Plotkin bound
editFor any R≤1−(qq−1)δ+o(1)
Gilbert–Varshamov bound
editJohnson bound
editLet C⊆𝔽qn of distance en≤q−1q(1−1−qq−1⋅dn)=Jq(dn)
Elias–Bassalygo bound
editSphere packings and lattices
editBlock codes are tied to the sphere packing problem which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is), the dimensions refer to the length of the codeword as defined above.
The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so-called perfect codes. There are very few of these codes.
Another property is the number of neighbors a single codeword may have. Again, consider pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. Respectively, in three and four dimensions, the maximum packing is given by the 12-face and 24-cell with 12 and 24 neighbors, respectively. When we increase the dimensions, the number of near neighbors increases very rapidly. In general, the value is given by the kissing numbers.
The result is that the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.
See also
editReferences
edit| View original on Wikipedia | Back | FazBrowse Home |