Block code

The data stream to be encoded is modeled as a string over some alphabet ${\displaystyle \Sigma }$. The size ${\displaystyle |\Sigma |}$ of the alphabet is often written as ${\displaystyle q}$. If ${\displaystyle q=2}$, then the block code is called a binary block code. In many applications it is useful to consider ${\displaystyle q}$ to be a prime power, and to identify ${\displaystyle \Sigma }$ with the finite field ${\displaystyle \mathbb {F} _{q}}$.

Messages are elements ${\displaystyle m}$ of ${\displaystyle \Sigma ^{k}}$, that is, strings of length ${\displaystyle k}$. Hence the number ${\displaystyle k}$ is called the message length or dimension of a block code.

The block length ${\displaystyle n}$ of a block code is the number of symbols in a block. Hence, the elements ${\displaystyle c}$ of ${\displaystyle \Sigma ^{n}}$ are strings of length ${\displaystyle n}$ and correspond to blocks that may be received by the receiver. Hence they are also called received words. If ${\displaystyle c=C(m)}$ for some message ${\displaystyle m}$, then ${\displaystyle c}$ is called the codeword of ${\displaystyle m}$.

The rate of a block code is defined as the ratio between its message length and its block length:

${\displaystyle R=k/n}$.

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 ${\displaystyle 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 ${\displaystyle 1}$ since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code ${\displaystyle C}$ is an injective map.

The distance or minimum distance d of a block code is the minimum number of positions in which any two distinct codewords differ, and the relative distance ${\displaystyle \delta }$ is the fraction ${\displaystyle d/n}$. Formally, for received words ${\displaystyle c_{1},c_{2}\in \Sigma ^{n}}$, let ${\displaystyle \Delta (c_{1},c_{2})}$ denote the Hamming distance between ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$, that is, the number of positions in which ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ differ. Then the minimum distance ${\displaystyle d}$ of the code ${\displaystyle C}$ is defined as

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$.

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 ${\displaystyle 1}$. Besides, the distance equals the minimum weight for linear block codes because:

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$.

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 d allows the receiver to detect up to ${\displaystyle d-1}$ transmission errors since changing ${\displaystyle d-1}$ positions of a codeword can never accidentally yield another codeword. Furthermore, if no more than ${\displaystyle (d-1)/2}$ 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 ${\displaystyle (d-1)/2}$. If more than ${\displaystyle (d-1)/2}$ 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.

The notation ${\displaystyle (n,k,d)_{q}}$ describes a block code over an alphabet ${\displaystyle \Sigma }$ of size ${\displaystyle q}$, with a block length ${\displaystyle n}$, message length ${\displaystyle k}$, and distance ${\displaystyle d}$. If the block code is a linear block code, then the square brackets in the notation ${\displaystyle [n,k,d]_{q}}$ are used to represent that fact. For binary codes with ${\displaystyle q=2}$, the index is sometimes dropped. For maximum distance separable codes, the distance is always ${\displaystyle d=n-k+1}$, but sometimes the precise distance is not known, non-trivial to prove or state, or not needed. In such cases, the ${\displaystyle d}$-component may be missing.

Sometimes, especially for non-block codes, the notation ${\displaystyle (n,M,d)_{q}}$ is used for codes that contain ${\displaystyle M}$ codewords of length ${\displaystyle n}$. For block codes with messages of length ${\displaystyle k}$ over an alphabet of size ${\displaystyle q}$, this number would be ${\displaystyle M=q^{k}}$.

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$ is called family of codes, where ${\displaystyle C_{i}}$ is an ${\displaystyle (n_{i},k_{i},d_{i})_{q}}$ code with monotonic increasing ${\displaystyle n_{i}}$.

Rate of family of codes C is defined as ${\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}$

Relative distance of family of codes C is defined as ${\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}$

To explore the relationship between ${\displaystyle R(C)}$ and ${\displaystyle \delta (C)}$, a set of lower and upper bounds of block codes are known.

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

The Singleton bound is that the sum of the rate and the relative distance of a block code cannot be much larger than 1:

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$.

In other words, every block code satisfies the inequality ${\displaystyle k+d\leq n+1}$. Reed–Solomon codes are non-trivial examples of codes that satisfy the singleton bound with equality.

For ${\displaystyle q=2}$, ${\displaystyle R+2\delta \leq 1}$. In other words, ${\displaystyle k+2d\leq n}$.

For the general case, the following Plotkin bounds holds for any ${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$ with distance d:

1. If ${\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}$
2. If ${\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}$

For any q-ary code with distance ${\displaystyle \delta }$, ${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$, where ${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}$, ${\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}$ is the q-ary entropy function.

Define ${\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$.
Let ${\displaystyle J_{q}\left(n,d,e\right)}$ be the maximum number of codewords in a Hamming ball of radius e for any code ${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$ of distance d.

Then we have the Johnson Bound : ${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$, if ${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}$

${\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$