# Coding theory

## Coding theory Topics

Sort by:

### Cyclic code

A linear code is cyclic if for every codeword in , the codeword is also in .

### Upc

The universal product code (UPC) is a 12-digit number and associated machine-readable bar code used to identify products being purchased in grocery stores. UPCs encode an individual product, but not its price (this part is done by a store's computer after reading the product identifier). The UPC is maintained by the Uniform Code Council of Dayton, Ohio. The first and last digits are separated from the others and written in a smaller font size.The first six digits are a manufacturer identifier, and the next five digits identify a specific product. The last digit is a check digit obtained from(1)where (mod 10) indicates taking the remainder after dividing by 10. For example, the UPC for Tropicana Pure Premium orange juice is(2)where the check digit is(3)(4)(5)(6)as expected.

### Isbn

An International Standard Book Number (ISBN) is a code used to uniquely identify a book together. It also uniquely encodes the book's publisher and includes information about its language of authorship. The original 10-"digit" ISBN-10 (where a "digit" consists of a decimal digit 0-9 for the first 9 places and 0-9 or X for the tenth place, corresponding to a mixed base string), in use for more than 30 years, was officially replaced with a 13-digit ISBN-13 (where each place is truly a decimal digit) as of Jan. 1, 2007.The digits of an ISBN are arranged in four groups (for an ISBN-10) or five groups (for an ISBN-13), which are sometimes (but not always) separated by hyphens. At present, an ISBN-13 is always prefixed by the digits 978 (US ISBN Agency). The first group in ISBN-10 or the second group for an ISBN-13 is a single digit which encodes country or language in which a publisher is incorporated: 0 for English, 2 for French,..

### Huffman coding

A lossless data compression algorithm which uses a small number of bits to encode common characters. Huffman coding approximates the probability for each character as a power of 1/2 to avoid complications associated with using a nonintegral number of bits to encode characters using their actual probabilities.Huffman coding works on a list of weights by building an extended binary tree with minimum weighted external path length and proceeds by finding the two smallest s, and , viewed as external nodes, and replacing them with an internal node of weight . The procedure is them repeated stepwise until the root node is reached. An individual external node can then be encoded by a binary string of 0s (for left branches) and 1s (for right branches).The procedure is summarized below for the weights 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41 given by the first 13 primes, and the resulting tree is shown above (Knuth 1997, pp. 402-403). As is clear..

### Codeword

A codeword is an element of an error-correcting code . If has length , then a codeword in has the form , where each is a letter in the alphabet of .

### Hamming code

A binary Hamming code of length (with ) is a linear code with parity-check matrix whose columns consist of all nonzero binary vectors of length , each used once (MacWilliams and Sloane 1977). is an code. Hamming codes are perfect single error-correcting codes.

### Perfect code

Let be an error-correcting code consisting of codewords,in which each codeword consists of letters taken from an alphabet of length , and every two distinct codewords differ in at least places. Then is said to be perfect if for every possible word of length with letters in , there is a unique code word in in which at most letters of differ from the corresponding letters of .It is straightforward to show that is perfect ifIf is a binary linear code, then and , where is the number of generators of , in which case is perfect ifHamming codes and the Golaycode are the only nontrivial examples of perfect codes.

### Parity check matrix

Given a linear code of length and dimension over the field , a parity check matrix of is a matrix whose rows generate the orthogonal complement of , i.e., an element of is a codeword of iff . The rows of generate the null space of the generator matrix .

### Gray code

A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, or more specifically still, the binary reflected Gray code.To convert a binary number to its corresponding binary reflected Gray code, start at the right with the digit (the th, or last, digit). If the is 1, replace by ; otherwise, leave it unchanged. Then proceed to . Continue up to the first digit , which is kept the same since is assumed to be a 0. The resulting number is the reflected binary Gray code.To convert a binary reflected Gray code to a binary number, start again with the th digit, and computeIf is 1, replace by ; otherwise, leave it the unchanged. Next computeand so on. The resulting number is the binary number corresponding to the initial binary reflected Gray code.The code is called reflected because it can be generated in the following manner. Take the Gray code 0, 1. Write..

### Golay code

The Golay code is a perfect linear error-correcting code. There are two essentially distinct versions of the Golay code: a binary version and a ternary version.The binary version is a binary linear code consisting of codewords of length 23 and minimum distance 7. The ternary version is a ternary linear code, consisting of codewords of length 11 with minimum distance 5.A parity check matrix for the binary Golay code is given by the matrix , where is the identity matrix and is the matrixBy adding a parity check bit to each codeword in , the extended Golay code , which is a nearly perfect binary linear code, is obtained. The automorphism group of is the Mathieu group .A second generator is the adjacency matrix for the icosahedron, with appended, where is a unit matrix and is an identity matrix.A third generator begins a list with the 24-bit 0 word (000...000) and repeatedly appends first 24-bit word that has eight or more differences from all words in the list...

### Cyclic redundancy check

A sophisticated checksum (often abbreviated CRC), which is based on the algebra of polynomials over the integers (mod 2). It is substantially more reliable in detecting transmission errors, and is one common error-checking protocol used in modems. The CRC is a form of hash function.To compare large data blocks using the CRC, first precalculate the CRCs for each block. Two blocks can then be rapidly compared by seeing if their CRCs are equal, saving a great deal of calculation time in most cases. The method is not infallible since for an -bit checksum, of random blocks will have the same checksum for inequivalent data blocks. However, if is large, the probability that two inequivalent blocks have the same CRC can be made very small.

### Nearly perfect code

Let be an error-correcting code consisting of codewords in which each codeword consists of letters taken from an alphabet of length , and every two distinct codewords differ in at least places. Then is said to be nearly perfect if, for every possible word of length with letters in , there is a codeword in in which at most letters of differ from the corresponding letters of . The codeword is unique if it differs from in fewer than places and there is at most one other codeword differing from in places if differs from in places.A nearly perfect code can be derived from a perfect code by adding a parity check digit to the end of each codeword in , so if is a -perfect binary linear code, then is a -nearly perfect binary linear code. In this way, the nearly perfect extended Golay code can be obtained from the perfect Golay code and the nearly perfect extended Hamming codes from the perfect Hamming codes...

### Generator matrix

Given a linear code , a generator matrix of is a matrix whose rows generate all the elements of , i.e., if , then every codeword of can be represented asin a unique way, where .An example of a generator matrix is the Golay code, which consists of all possible binary sums of the 11 rows.

### Linear code

A linear code over a finite field with elements is a linear subspace . The vectors forming the subspace are called codewords. When codewords are chosen such that the distance between them is maximized, the code is called error-correcting since slightly garbled vectors can be recovered by choosing the nearest codeword.

### Encoding

An encoding is a way of representing a number or expression in terms of another (usually simpler) one. However, multiple expressions can also be encoded as a single expression, as in, for example,which encodes and uniquely as a single number.000011102023114205More generally, any list of positive integers can be uniquely encoded using a Gödel number (Wolfram 2002, p. 1120).

### Barker code

A Barker code is a string of digits of length such thatfor all . Barker codes are used for pulse compression of radar signals. There are Barker codes of lengths 2, 3, 4, 5, 7, 11, and 13, and it is conjectured that no longer Barker codes exist. A list of known Barker codes up to reversal of digits and negation is given below.lengthcode2, 34, 571113The number of candidate codes of length is therefore equal to the number of -bead black-white reversible strings 1, 2, 3, 6, 10, 20, 36, 72, ... (OEIS A005418), while the numbers of Barker codes of order , 3, ... are 2, 1, 2, 1, 0, 1, 0, 0, 0, 1, 0, 1, and 0 for all higher (OEIS A091704).