Block code
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, and Reed–Muller 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. The term "block code" may also refer to any error-correcting code that acts on a block of formula_1 bits of input data to produce formula_2 bits  of output data formula_3. Consequently, the block coder is a "memoryless" device. Under this definition codes such as turbo codes, terminated convolutional codes and other iteratively decodable codes (turbo-like codes) would also be considered block codes. A non-terminated convolutional encoder would be an example of a non-block (unframed) code, which has "memory" and is instead classified as a "tree code". This article deals with "algebraic block codes". The block code and its parameters. Error-correcting codes are used to reliably transmit digital data over unreliable communication channels subject to channel noise. When a sender wants to transmit  a possibly very long data stream using a block code, the sender breaks the stream up into pieces of some fixed size. Each such piece is called "message" and the procedure given by the block code encodes each message individually into a codeword, also called a "block" in the context of block codes. The sender then transmits all blocks to the receiver, who can in turn use some decoding mechanism to (hopefully) recover the original messages from the possibly corrupted received blocks. The performance and success of the overall transmission depends on the parameters of the channel and the block  code. Formally, a block code is an injective mapping Here, formula_5 is a finite and nonempty set and formula_1 and formula_2 are integers. The meaning and significance of these three parameters and other parameters related to the code are described below. The alphabet Σ. The data stream to be encoded is modeled as a string over some alphabet formula_5. The size formula_9 of the alphabet is often written as formula_10. If formula_11, then the block code is called a "binary" block code. In many applications it is useful to consider formula_10 to be a prime power, and to identify formula_5  with the finite field formula_14. The message length "k". Messages are elements formula_15 of formula_16, that is, strings of length formula_1. Hence the number formula_1 is called the message length or dimension of a block code. The block length "n". The block length formula_2 of a block code is the number of symbols in a block. Hence, the elements formula_20 of formula_21 are strings of length formula_2 and correspond to blocks that may be received by the receiver. Hence they are also called received words. If formula_23 for some message formula_15, then formula_20 is called the codeword of formula_15. The  rate "R". The rate of a block code is defined as the ratio between its message length and its block length: A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity formula_28 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 formula_29 since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code formula_30 is an injective map. The  distance "d". The distance or minimum distance of a block code is the minimum number of positions in which any two distinct codewords differ, and the relative distance formula_31 is the fraction formula_32. Formally, for received words formula_33, let formula_34 denote the Hamming distance between formula_35 and formula_36, that is, the number of positions in which formula_35 and formula_36 differ. Then the minimum distance formula_39 of the code formula_30 is defined as Since any code has to be injective, any two codewords will disagree in at least one position, so the distance of any code is at least formula_29. Besides , the distance equals the minimum weight for linear block codes because: A larger distance allows for more error correction and detection. For example, if we only consider errors that may change symbols of the sent codeword but never erase or add them, then the number of errors is the number of positions in which the sent codeword and the received word differ. A code with distance allows the receiver to detect up to formula_44 transmission errors since changing formula_44 positions of a codeword can never accidentally yield another codeword. Furthermore, if no more than formula_46 transmission errors occur, the receiver  can uniquely decode the received word to a codeword. This is because every received word has at most one codeword at distance formula_46. If more than formula_46 transmission errors occur, the receiver cannot uniquely decode the received word in general as there might be several possible codewords. One way for the receiver to cope with this situation is to use list decoding, in which the decoder outputs a list of all codewords in a certain radius. Popular notation. The notation formula_49 describes a block code over an alphabet formula_5 of size formula_10, with a block length formula_2, message length  formula_1, and distance formula_39. If the block code is a linear block code, then the square brackets in the notation formula_55 are used to represent that fact. For binary codes with formula_11, the index is sometimes dropped. For maximum distance separable codes, the distance is always formula_57, but sometimes the precise distance is not known, non-trivial to prove or state, or not needed. In such cases, the formula_39-component may be missing. Sometimes, especially for non-block codes, the notation formula_59 is used for codes that contain formula_60 codewords of length formula_2. For block codes with messages of length  formula_1 over an alphabet of size formula_10, this number would be formula_64. Examples. As mentioned above, there are a vast number of error-correcting codes that are actually block codes. The first error-correcting code was the Hamming(7,4) code, developed by Richard W. Hamming in 1950. This code transforms a message consisting of 4 bits into a codeword of 7 bits by adding 3 parity bits. Hence this code is a block code. It turns out that it is also a linear code and that it has distance 3. In the shorthand notation above, this means that the Hamming(7,4) code  is a formula_65 code. Reed–Solomon codes are a family of formula_55 codes with formula_57 and formula_10 being a prime power. Rank codes are family of formula_55 codes with formula_70. Hadamard codes are a family of formula_71 codes with formula_72 and formula_73. Error detection and correction properties. A codeword formula_74could be considered as a point in the formula_2-dimension space formula_21 and the code formula_77 is the subset of formula_21. A code formula_77 has distance formula_39 means that formula_81, there is no other codeword in the "Hamming ball" centered at formula_20 with radius formula_44, which is defined as the collection  of formula_2-dimension words whose "Hamming distance" to formula_20 is no more than formula_44. Similarly, formula_87 with (minimum) distance formula_39 has the following properties: Let formula_97 be the maximum number of codewords in a Hamming ball of radius for any code formula_98 of distance . Then we have the "Johnson Bound" : formula_99, if formula_100 Sphere packings and lattices. Block 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.