Editing Coding theory (section)

====Linear block codes====
{{Main|Block code}}

Linear block codes have the property of [[linearity]], i.e. the sum of any two codewords is also a code word, and they are applied to the source bits in blocks, hence the name linear block codes. There are block codes that are not linear, but it is difficult to prove that a code is a good one without this property.<ref name=terras/>

Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (''n'',''m'',''d<sub>min</sub>'')<ref name=blahut/> where

# n is the length of the codeword, in symbols,
# m is the number of source symbols that will be used for encoding at once,
# ''d<sub>min</sub>'' is the minimum hamming distance for the code.

There are many types of linear block codes, such as

# [[Cyclic code]]s (e.g., [[Hamming code]]s)
# [[Repetition code]]s
# [[Parity bit|Parity codes]]
# [[Polynomial code]]s (e.g., [[BCH code]]s)
# [[Reed–Solomon error correction|Reed–Solomon codes]]
# [[Algebraic geometric code]]s
# [[Reed–Muller code]]s
# [[Hamming bound|Perfect codes]]
# [[Locally recoverable code]]

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 (24,12) [[Binary Golay code|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. The only nontrivial and useful perfect codes are the distance-3 Hamming codes with parameters satisfying (2<sup>''r''</sup> – 1, 2<sup>''r''</sup> – 1 – ''r'', 3), and the [23,12,7] binary and [11,6,5] ternary Golay codes.<ref name=terras>
{{cite book | title = Fourier Analysis on Finite Groups and Applications |first=Audrey |last=Terras |author-link=Audrey Terras| publisher = [[Cambridge University Press]] | year = 1999 | isbn = 978-0-521-45718-7 | url = https://archive.org/details/fourieranalysiso0000terr | url-access = registration | page = [https://archive.org/details/fourieranalysiso0000terr/page/195 195] }}</ref><ref name=blahut>{{cite book |title = Algebraic Codes for Data Transmission |first=Richard E. |last=Blahut |author-link=Richard E. Blahut | publisher = Cambridge University Press | year = 2003 | isbn = 978-0-521-55374-2 | url = https://books.google.com/books?id=n0XHMY58tL8C&pg=PA60}}
</ref>

Another code property is the number of neighbors that a single codeword may have.<ref name=schlegel>
{{cite book
 | title = Trellis and turbo coding
 |author1=Christian Schlegel |author2=Lance Pérez | publisher = Wiley-IEEE
 | year = 2004
 | isbn = 978-0-471-22755-7
 | page = 73
 | url = https://books.google.com/books?id=9wRCjfGAaEcC&pg=PA73
 }}</ref>
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. When we increase the dimensions, the number of near neighbors increases very rapidly.  The result is 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.<ref name=schlegel/>

Properties of linear block codes are used in many applications.  For example, the syndrome-coset uniqueness property of linear block codes is used in trellis shaping,<ref>{{cite journal |first=G.D. Jr. |last=Forney |author-link=Dave Forney |title=Trellis shaping |journal=IEEE Transactions on Information Theory |volume=38 |issue=2 Pt 2 |pages=281–300 |date=March 1992 |doi=10.1109/18.119687 |s2cid=37984132 }}</ref> one of the best-known [[shaping codes]].