Linear code

In coding theory, a linear code is a special kind of error-correcting code. It has a very useful property: if you combine any two codewords in a certain mathematical way, called a linear combination, the result is also a codeword. This makes linear codes easier to work with than other kinds of codes. Linear codes are divided into two main types: block codes and convolutional codes, with some newer codes like turbo codes mixing features of both.

Linear codes are very important for sending information over things like the internet or wireless signals. They help catch and fix mistakes that happen when messages travel through a communications channel. For example, when sending a message made of bits, a linear code adds extra bits so the receiver can spot and fix errors. One famous example is the [7,4,3] Hamming code, a binary code that takes a 4-bit message and turns it into a 7-bit codeword. Because of how these codewords are built, this code can detect up to two mistakes in each message and fix one mistake.

Definition and parameters

A linear code is a special kind of code used to correct errors when sending information. It works by using a set of special messages called codewords. These codewords follow strict rules: if you combine any two codewords using simple addition, the result is always another codeword in the set.

We describe a linear code by three numbers: its length (how many pieces of information it contains), its dimension (how many special messages we can create from it), and its distance (how different the messages are from each other). This helps us understand how well the code can correct mistakes during transmission.

Generator and check matrices

A linear code can be described using special tables called matrices. One type is called a generating matrix, which helps create all the codewords in the code. Another type is called a check matrix, which helps verify if a message follows the code's rules.

These matrices make working with linear codes easier, allowing computers to encode and decode messages efficiently. The design of these matrices is important for ensuring that errors can be detected and corrected effectively.

Example: Hamming codes

Main article: Hamming code

Hamming codes are a type of linear code used to fix small mistakes in digital messages. For any number r that is 2 or larger, there is a special Hamming code that can fix one wrong bit in a row of bits.

For example, there is a Hamming code that works with 7 bits and can tell you which one of the 4 important bits might be wrong. It uses special patterns of bits to check and fix mistakes.

Example: Hadamard codes

Main article: Hadamard code

A Hadamard code is a special type of linear code that can correct many errors. It is built by using the binary representation of numbers to create its codewords. This code has a minimum distance, which means it can detect and fix a certain number of errors in the data.

For example, one type of Hadamard code uses an 8-bit block to encode 3 bits of information, and it can correct up to 1 error. This code is related to another code called the Reed–Muller code. By removing one column from the Hadamard code, we get a simpler code called the simplex code, which is connected to the Hamming code.

Nearest neighbor algorithm

The nearest neighbor algorithm helps fix mistakes in data by finding the closest correct message. It starts by looking at the received message and checks if it matches any known correct messages. If not, it expands the search step by step until it finds a match or determines there is no correct match nearby.

This method is important because it shows how many mistakes a code can correct based on its design. The algorithm repeats steps, increasing the search area each time, until it either finds a correct message or confirms that none exists within the expected error range.

Popular notation

Main article: Block code § Popular notation

In coding, we often use the letter C to stand for a code. A code that has a certain length n and a rank k (meaning it has n code words in its basis) is called an (n, k) code. For linear block codes, we often write them as [n, k, d] codes, where d tells us the smallest difference between any two code words. This helps us understand how good the code is at fixing mistakes.

Singleton bound

The Singleton bound is a rule that helps us understand the limits of linear codes, which are special ways to correct errors in data. It says that for any linear code with certain properties, the numbers that describe it must follow a simple formula: k + d ≤ n + 1.

Codes that meet this rule exactly—where k + d = n + 1—are called maximum distance separable or MDS codes. These codes are considered the best possible in some ways because they achieve the highest error-correcting ability for their size.

Bonisoli's theorem

A code is equidistant if the distance between any two different codewords is always the same number, called d. In 1984, Arrigo Bonisoli studied special types of codes called linear one-weight codes and showed that every equidistant linear code is related to a sequence of dual Hamming codes. This helps mathematicians understand the structure of these codes better.

Examples

Linear codes are special types of codes used to fix mistakes when information is sent or stored. Some examples of linear codes are:

• Repetition code
• Parity code
• Cyclic code
• Hamming code
• Golay code, both the binary and ternary versions
• Polynomial codes, of which BCH codes are an example
• Reed–Solomon codes
• Reed–Muller code
• Algebraic geometry code
• Binary Goppa code
• Low-density parity-check codes
• Expander code
• Multidimensional parity-check code
• Toric code
• Turbo code
• Locally recoverable code

These codes help make sure information stays safe and clear, even if some parts get mixed up.

Generalization

Hamming spaces over non-field alphabets have been studied, especially over finite rings such as Galois rings over Z₄. This leads to modules instead of vector spaces and what are called ring-linear codes instead of linear codes. The Lee distance is often used as a measure in these cases. There is also a special mapping, called a Gray isometry, that connects certain codes using different distance measures. Some researchers also use the term "linear codes" for these codes over rings.