Coding theory

Plaintext is the unencrypted message supplied to a cipher.

Ciphertext

 2  0

Ciphertext is the encrypted message produced by a cipher.

Error-correcting code

An error-correcting code is a set of codewords chosen with enough separation to detect or correct transmission errors.

Repetition code

A binary repetition code represents one bit by repeating it a fixed number of times. Majority decoding corrects fewer than half as many bit flips as the block length.

Hamming distance ( $d_{H}$ )

The Hamming distance between two equal-length words is the number of coordinates in which they differ.

Normalized Hamming distance ( $\overline{d}_{H} (x, y) = d_{H} (x, y) / n$ )

On binary words of length

n

, normalized Hamming distance is the fraction of differing coordinates. Unlike unscaled Hamming distance, it makes the Hamming cubes a Lévy family under uniform probability measures.

Hamming cube ( ${- 1, 1}^{n}$ )

The Hamming cube is

{- 1, 1}^{n}

, or equivalently

{0, 1}^{n}

, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters

n, 1/2

. This converts geometric ball sizes into probability tails.

Exponential packing of a Hamming cube ( $∣ S ∣ \geq e^{9 n /32}, d_{H} (s, s^{'}) \geq n /8$ )

An inclusion-maximal separated set of separation

an

covers the Hamming cube by strict-radius

an

balls. The Hoeffding lower-tail bound for Hamming balls then gives at least

e^{2 n (1/2 - a)^{2}}

selected vertices. At

a = 1/8

this yields

e^{9 n /32}

vertices, all separated by at least

n /8

Hamming distance between unlabelled bipartitions ( $Δ (S, T) = min {∣ S △ T ∣, ∣ S △ T^{c} ∣}$ )

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with

\pm 1

membership vectors, it is.

Sign rounding bound for a unit eigenvector ( $Δ (S, S) \leq n ∥ v v^{⊤} - v v^{⊤} ∥_{F}^{2}$ )

Suppose

v_{i} = \pm 1/ n

encodes the true partition and

v

is a unit estimated eigenvector. Every coordinate of the wrong sign contributes at least

1/ n

min_{σ = \pm 1} ∥ v - σ v ∥_{2}^{2} = 2 (1 - ∣ v^{⊤} v ∣)

. Since this is at most

2 (1 - ∣ v^{⊤} v ∣^{2})

, which is the squared Frobenius distance between the rank-one orthogonal projection matrices, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.

Minimum distance of a code ( $d (C)$ )

The minimum distance of a code

C

is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

Hamming ball ( $B_{r} (x)$ )

The Hamming ball of radius

r

about a word

x

is the set of words whose Hamming distance from

x

is at most

r

Hoeffding lower-tail bound for Hamming balls ( $2^{- n} ∣ B_{an} ∣ \leq e^{- 2 n (1/2 - a)^{2}}$ )

For a uniform vertex of the Hamming cube, distance from a fixed vertex is the sum of

n

independent Bernoulli random variables with parameter

1/2

. The lower-tail Hoeffding inequality implies that the fraction of vertices at distance at most

an

0 < a < 1/2

, is at most

e^{- 2 n (1/2 - a)^{2}}

. Strict-radius balls satisfy the same upper bound.

Entropy bound for a Hamming ball ( $\sum_{j \leq ρ n} (j n) \leq e^{nh (ρ)}$ )

For

0 < ρ \leq 1/2

, the number of binary words within Hamming distance

ρ n

of a fixed word is at most

e^{nh (ρ)}

, with the binary entropy function in natural logarithms. In

1 = \sum_{j} (j n) ρ^{j} (1 - ρ)^{n - j}

, each summand weight for

j \leq ρ n

is at least

ρ^{ρ n} (1 - ρ)^{n (1 - ρ)} = e^{- nh (ρ)}

. Also

h^{''} (ρ) = - 1/ (ρ (1 - ρ)) \leq - 4

, so

lo g 2 - h (1/2 - a) \geq 2 a^{2}

. These two bounds give the approximate-recovery denominator in the list-decoding Fano inequality.

Perfect code

A code of minimum distance

d

is perfect if its Hamming balls of radius

⌊(d - 1) /2 ⌋

partition the ambient word space. Every word then has a unique nearest codeword within the code's error-correction radius.

Singleton bound

For a code of length

n

, size

M

, and minimum distance

d

over an alphabet of size

q

, puncturing

d - 1

coordinates gives the Singleton bound

M \leq q^{n - d + 1} .

Plotkin bound

The Plotkin bound limits a code whose minimum distance is more than the average distance between unrestricted words. For a binary code with

n < 2 d

and even

d

M \leq 2 ⌊ \frac{d}{2 d - n} ⌋ .

Puncturing (coding theory)

Punctured code

Puncturing a code at one coordinate deletes that coordinate from every codeword. For a code of minimum distance

d \geq 2

, puncturing preserves its number of words and gives minimum distance

d

d - 1

One-time pad

 2  0

For messages in a finite additive group, a one-time pad encrypts

X

C = X + K

, where the key

K

is uniform and independent of

X

, as long as the message, and never reused. Then

C

is uniform and independent of

X

, giving perfect secrecy.

Two-time pad attack

If two plaintexts are encrypted by adding the same one-time-pad key, subtracting the ciphertexts cancels the key and reveals the difference of the plaintexts. Redundancy in natural language or another structured message space can then reveal both messages, so a one-time pad must never reuse key material.

Perfect secrecy

An encryption scheme has perfect secrecy when the ciphertext and plaintext are independent random variables, so observing the ciphertext does not change the plaintext's probability distribution.

Malleability of an additive one-time pad

If an interceptor knows that an additive one-time-pad ciphertext

C

encrypts plaintext

P

and wants it to decrypt as

P^{'}

, replacing it by

C^{'} = C - P + P^{'}

works without knowing the key, since

C^{'} = P^{'} + K

Perfect secrecy of Shamir's threshold scheme

Conditioned on any

r - 1

shares in Shamir's secret sharing, each candidate secret in

F_{p}

remains equally likely. Appending

(0, N)

to those shares determines exactly one degree-at-most-

(r - 1)

polynomial for every candidate

N

, by the nonzero Vandermonde determinant.

Discrete memoryless channel

A discrete memoryless channel has finite input and output alphabets and transition probabilities

P (y ∣ x)

. Conditional on the input symbols, different channel uses have independent outputs governed by the same transition probabilities.

Finite-alphabet erasure channel ( $Y = X with probability 1 - f, Y = e with probability f$ )

A finite-alphabet erasure channel transmits the input symbol unchanged with probability

1 - f

and replaces it by a distinct erasure flag with probability

f

, independently of the symbol. Given the flag, the posterior remains the input distribution; otherwise the input is known. Thus its mutual information is

(1 - f) H (X)

Capacity of a finite-alphabet erasure channel ( $C = (1 - f) lo g_{2} k$ )

For a finite-alphabet erasure channel with

k

input symbols,

I (X; Y) = (1 - f) H (X)

. Maximizing Shannon entropy at the uniform input gives channel capacity

C = (1 - f) lo g_{2} k

bits per use, by the Shannon second coding theorem.

Binary erasure channel

A binary erasure channel transmits each input bit correctly with probability

1 - ε

and replaces it by an erasure symbol with probability

ε

. Its channel capacity is

1 - ε

bits per use.

Z-channel

A Z-channel transmits one binary input without error while the other can change into the first. Unlike a binary symmetric channel, its errors are one-sided.

Shannon second coding theorem

For a discrete memoryless channel, operational capacity equals

C = max_{P_{X}} I (X; Y) .

Rates below

C

admit codes whose error tends to zero, while rates above

C

cannot have vanishing error.

Reliable transmission rate ( $R$ )

A rate

R

is reliably achievable through a channel when there is a sequence of length-

n

channel codes with

M_{n}

messages such that

lim inf_{n \to \infty} \frac{l o g _{2} M _{n}}{n} \geq R

and their decoding-error probability tends to zero.

Linear-feedback shift register

A binary linear-feedback shift register of degree

d

updates a

d

-bit state by shifting and inserting a fixed linear combination over

F_{2}

. With recurrence

s_{n + d} = a_{d - 1} s_{n + d - 1} + \dots + a_{0} s_{n},

its feedback polynomial is

x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{0}

Feedback polynomial

The feedback polynomial records the coefficients of an LFSR recurrence. With the convention

s_{n + d} = a_{d - 1} s_{n + d - 1} + \dots + a_{0} s_{n},

it is

x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{0}

Feedback shift register

A feedback shift register updates a finite state by shifting its stored symbols and inserting the value of a feedback function of the previous state. The feedback function need not be linear.

Berlekamp-Massey algorithm

The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.

Minimal recurrence for the binary prefix 11001011

The shortest binary linear recurrence producing the prefix

11001011

has length three:

x_{n} = x_{n - 2} + x_{n - 3} .

Its connection polynomial is

1 + D^{2} + D^{3}

Period bound for a linear-feedback shift register

A degree-

d

binary register has

2^{d}

states. The zero state is fixed, so a nonzero periodic orbit has length at most

2^{d} - 1

Feedback-polynomial parity condition for maximal period

A maximal-period feedback polynomial cannot have

1

as a root. Over

F_{2}

, this says

1 + a_{d - 1} + \dots + a_{0} \neq = 0,

so an even number of the coefficients

a_{i}

equal one and the full monic polynomial has an odd number of nonzero coefficients.

Zero-run lower bound for a linear-feedback shift register

If an output prefix contains

d

consecutive zeros followed by a one, no register of degree at most

d

can generate it: the all-zero state would have been reached and would remain zero forever.

Minimal linear-feedback shift register for the prefix 100000001

The seven consecutive zeros followed by one force degree at least eight. Degree eight is attained by

s_{n + 8} = s_{n}

, with initial state

10000000

and feedback polynomial

x^{8} + 1

Trace-generated maximal-period linear-feedback sequence

Let

K = F_{2^{d}}

, let

α

generate

K^{\times}

, and let

T : K \to F_{2}

be nonzero linear with nondegenerate bilinear form

(x, y) \mapsto T (x y)

. If the minimal polynomial of

α

P (X) = X^{d} + \sum_{j < d} c_{j} X^{j}

, then

x_{n} = T (α^{n})

satisfies

x_{n + d} = \sum_{j < d} c_{j} x_{n + j},

so it is produced by an LFSR of length at most

d

. Its period is exactly

2^{d} - 1

: any period

r

would imply

T ((α^{r} - 1) y) = 0

for every

y \in K

, hence

α^{r} = 1

by nondegeneracy.

Linear code

A binary linear

[n, k, d]

code is a

k

-dimensional subspace of

F_{2}^{n}

with least nonzero weight

d

. A parity-check matrix presents it as a kernel.

Tetracode ( $T \leq F_{3}^{4}$ )

The two-dimensional ternary linear code generated by

(0, 1, 1, 1)

and

(1, 1, - 1, 0)

. Its eight nonzero words have exactly three nonzero entries, with precisely two opposite words for each position of the zero coordinate.

Weight enumerator ( $W_{C} (s, t)$ )

The homogeneous weight enumerator of a length-

n

linear code

C

is the polynomial

W_{C} (s, t) = \sum_{x \in C} s^{wt (x)} t^{n - wt (x)} .

Its coefficients count words of each Hamming weight. In this convention

W_{C} (1, 1) = ∣ C ∣

; some references interchange

s, t

MacWilliams identity

For a binary linear code of dimension

k

and its dual code, the weight enumerator convention

s^{wt (x)} t^{n - wt (x)}

gives

W_{C^{⊥}} (s, t) = 2^{- k} W_{C} (t - s, t + s) .

To prove it, insert

1_{C^{⊥}} (y) = 2^{- k} \sum_{x \in C} (- 1)^{x \cdot y}

into the enumerator sum. Summing independently over each coordinate of

y

yields a factor

t + s

x_{j} = 0

and

t - s

x_{j} = 1

Parity bit

A parity bit records whether the number of one bits in a word is even or odd and can detect every error that flips an odd number of bits.

Parity computation by CNOT gates ( $W ∣ x ⟩ ∣ y ⟩ = ∣ x ⟩ ∣ y \oplus ⨁_{j} x_{j} ⟩$ )

Apply one CNOT gate from each input qubit to the same target. Their actions commute because controls remain unchanged and each contribution is added modulo two. This reversible circuit computes the parity bit with exactly one two-qubit gate per input, and its inverse is the same circuit. Unlike measuring the inputs to compute parity classically, the unitary preserves quantum superposition and can be uncomputed after phase application.

Even-weight binary code

The length-

n

even-weight code consists of binary words whose coordinates sum to zero. It has parameters

[n, n - 1, 2]

Binary repetition code

The binary repetition code is

{0^{n}, 1^{n}}

and has parameters

[n, 1, n]

Zero code

The zero code contains only the zero word and has dimension zero.

Whole-space linear code

The whole-space binary code is

F_{2}^{n}

, with parameters

[n, n, 1]

Hamming weight ( $wt$ )

The Hamming weight

wt (x)

of a word is the number of its nonzero coordinates.

Minimum Hamming distance of a linear code ( $d$ )

The minimum Hamming distance of a nonzero linear code is the smallest Hamming weight of a nonzero codeword.

Griesmer bound

Every binary linear

[n, k, d]

code satisfies

n \geq \sum_{j = 0}^{k - 1} ⌈ \frac{d}{2 ^{j}} ⌉ .

Puncturing on the support of a minimum-weight codeword reduces the rank by one and leaves minimum distance at least

⌈ d /2 ⌉

, which proves the bound inductively.

Generator matrix ( $G$ )

A generator matrix for a linear code has a basis of the code as its rows, so its row space is the code.

Parity-check matrix ( $H$ )

A parity-check matrix

H

for a linear code

C

satisfies

C = ker H = {c : H c^{T} = 0} .

Syndrome ( $s = H y^{T}$ )

The syndrome of a received word

y

with respect to a parity-check matrix

H

s = H y^{T}

. It vanishes exactly when

y

is a codeword and otherwise identifies the coset containing the error pattern.

Parity-check extension of a linear code

The parity-check extension of a binary linear code appends to each codeword the sum of its coordinates in

F_{2}

, making every extended word have even Hamming weight.

Shortened code

Shortening a code at one coordinate first retains only words with a chosen symbol there and then applies puncturing at that coordinate. The minimum distance cannot decrease. In a binary code one coordinate-symbol fibre contains at least half of the words.

Dual code ( $C^{⊥}$ )

The dual code

C^{⊥}

consists of the words orthogonal to every word of

C

under the standard dot product. A parity-check matrix for

C

is a generator matrix for

C^{⊥}

Reed-Muller code

The binary Reed-Muller code

RM (d, r)

evaluates Boolean polynomials of degree at most

r

F_{2}^{d}

. It has parameters

[2^{d}, \sum_{j = 0}^{r} (j d), 2^{d - r}] .

The dimension counts square-free monomials, and the minimum weight follows inductively from the decomposition

(u, u + v)

Bar product of binary linear codes ( $C_{1} ∣ C_{2}$ )

For length-

n

binary linear codes

C_{2} \subseteq C_{1}

, their bar product is

C_{1} ∣ C_{2} = {(u, u + v) : u \in C_{1}, v \in C_{2}} .

It has length

2 n

and dimension

dim C_{1} + dim C_{2}

Minimum distance of a bar product

C_{2} \subseteq C_{1}

have minimum distances

d_{2}, d_{1}

, respectively, then

d (C_{1} ∣ C_{2}) = min (2 d_{1}, d_{2}) .

Indeed,

wt (u) + wt (u + v) \geq wt (v)

, while the words

(u, u)

and

(0, v)

attain the two candidate bounds.

Parity-check matrix of a bar product

H_{i}

is a parity-check matrix of

C_{i}

, then a parity-check matrix of

C_{1} ∣ C_{2}

(H_{1} H_{2} 0 H_{2}) .

Its equations say that the first half

u

lies in

C_{1}

and that the sum of the two halves lies in

C_{2}

Reed-Muller bar-product recursion

For

0 < r < d

RM (d, r) = RM (d - 1, r) ∣ RM (d - 1, r - 1) .

Consequently

dim RM (d, r) = \sum_{j = 0}^{r} (j d) .

(2)

Dual of a Reed-Muller code

Under the standard binary inner product,

RM (d, r)^{⊥} = RM (d, d - r - 1) .

The product of representing polynomials has degree at most

d - 1

, so its evaluation word has even weight; equality follows by comparing dimensions.

Hamming code

The binary Hamming code of redundancy

r

has parameters

[2^{r} - 1, 2^{r} - r - 1, 3]

. Its parity-check matrix has every nonzero vector of

F_{2}^{r}

as a column.

Binary simplex code

The binary simplex code is the dual of the binary Hamming code. For redundancy

r

it has parameters

[2^{r} - 1, r, 2^{r - 1}]

Perfectness of a Hamming code

A Hamming code has

2^{2^{r} - r - 1}

words, and each radius-one Hamming ball contains

1 + (2^{r} - 1) = 2^{r}

vectors. Its minimum distance is three, so these balls are disjoint, and their total size is

2^{2^{r} - 1}

. They therefore partition the ambient space, making the code perfect.

Minimum-distance error-detection and correction guarantee

A code of minimum Hamming distance

d

detects every pattern of at most

d - 1

errors and uniquely corrects every pattern of at most

⌊(d - 1) /2 ⌋

errors. The correction claim follows because Hamming balls of that radius around distinct codewords are disjoint.

Cyclic code

A length-

n

cyclic code over

F_{q}

is an ideal of

F_{q} [X] / (X^{n} - 1)

. It is generated by a monic divisor of

X^{n} - 1

Generator polynomial of a cyclic code ( $g (X)$ )

The unique monic divisor

g (X)

X^{n} - 1

generating a cyclic code is its generator polynomial. The code has dimension

n - de g g

Root-evaluation syndrome for a cyclic code

Let

α

be a root of the generator polynomial of a cyclic code

g (X)

. Every codeword

c (X)

satisfies

c (α) = 0

, so a received word

r = c + e

satisfies

r (α) = e (α)

. For a single-symbol error

e (X) = a X^{j}

, the evaluation

r (α) = a α^{j}

identifies its value and position when the relevant powers of

α

are distinct.

Dual of a cyclic code

The dual of a cyclic code is cyclic. If

g (X) h (X) = X^{n} - 1

, then the dual generator is the monic reciprocal polynomial

h^{*} (X)

Binary cyclic codes of length seven

Over

F_{2}

X^{7} - 1 = (X + 1) (X^{3} + X + 1) (X^{3} + X^{2} + 1) .

Its eight monic divisors generate the eight cyclic codes of length seven: the whole-space, even-weight, two Hamming, two simplex, repetition, and zero codes.

BCH code

Given a primitive

n

th root

α

, a BCH code of design distance

δ

has a generator polynomial vanishing at

δ - 1

consecutive powers

α^{b}, \dots, α^{b + δ - 2}

Error locator polynomial ( $σ (Z)$ )

For error locations

i_{1}, \dots, i_{ν}

in a cyclic code with primitive root

α

, the error locator polynomial is

σ (Z) = \prod_{h} (1 - α^{i_{h}} Z)

. Its roots encode the error positions.

BCH bound

The minimum distance of a BCH code is at least its design distance. A hypothetical word of smaller weight yields a square Vandermonde system from the consecutive-root equations; its support elements are distinct, so the determinant is nonzero and every word coefficient must vanish.

Parity extension

Appending a parity bit makes every word even-weight. A binary

[n, m, d]

code becomes an

[n + 1, m, d^{+}]

code, where

d^{+} = {d, d + 1, d even, d odd .

Hamming bound

A binary length-

n

code of size

M

and distance at least

2 t + 1

satisfies

M \sum_{j = 0}^{t} (j n) \leq 2^{n} .

Equality means the code is perfect.

Rabin cryptosystem

Rabin encryption sends

m

m^{2}

modulo a product of two secret primes. Decryption computes the four square roots by the Chinese remainder theorem.

Factorization from distinct square roots modulo a semiprime

N = pq

and

x^{2} \equiv y^{2} (mod N)

while

x \neq \equiv \pm y (mod N)

, then

N ∣ (x - y) (x + y),

and

g cd (x - y, N)

is a nontrivial factor of

N

Chosen-square attack on Rabin authentication

If a purported authentication service returns a square root of every chosen square modulo a Rabin modulus, a verifier who knows one root obtains a different root with substantial probability and can factor the modulus. Repeating the challenge therefore reveals the private key.

Discrete logarithm problem

Given a cyclic group generator

g

and an element

h

, the discrete logarithm problem asks for an exponent

a

such that

g^{a} = h

Diffie-Hellman key exchange

 2  0

Alice publishes

g^{a}

and Bob publishes

g^{b}

in a public cyclic group; each can then compute the shared secret

g^{ab}

. Its security relies on the difficulty of recovering the exponents or otherwise solving the computational Diffie--Hellman problem.

Unique decodability

Unique decodability means that every encoded message has at most one decomposition into codewords.

Decipherable code

A code is decipherable, or uniquely decodable, when every finite concatenation of codewords has at most one decomposition into source codewords.

Optimal source code (min∑a​pa​ℓa​)  0  0   
 
 Decipherable code

For a fixed source distribution and code alphabet, an optimal uniquely decodable code minimizes expected codeword length. Huffman coding gives an optimal binary prefix code, and the equivalence of attainable uniquely-decodable and prefix-code lengths gives the same minimum for both classes.

Prefix code

In a prefix code no codeword is the prefix of another, so concatenated messages have unique instantaneous decoding.

Kraft inequality

The lengths of every decipherable binary code satisfy

\sum_{i} 2^{- l_{i}} \leq 1.

Conversely, any positive integer lengths satisfying this bound can be realized by a prefix code.

McMillan inequality

The lengths of a finite uniquely decodable code satisfy

\sum_{a} 2^{- l (a)} \leq 1

, even when the code is not a prefix code. Distinct concatenations of

r

codewords remain distinct; counting the possible binary strings of each total length bounds

(\sum_{a} 2^{- l (a)})^{r}

r max_{a} l (a)

. Taking

r

th roots proves the claim.

Equivalence of decipherable and prefix code lengths

Prescribed positive word lengths admit a decipherable code if and only if they admit a prefix code. Counting length-

L

concatenations of

m

words proves the Kraft inequality for any decipherable code; choosing free vertices of the ordered

D

-ary tree constructs a prefix code whenever this inequality holds. Each prefix code has unique decodability.

Total length lower bound for a decipherable binary code

If a decipherable binary code has

N

codewords of lengths

l_{1}, \dots, l_{N}

, then

\sum_{i = 1}^{N} l_{i} \geq N lo g_{2} N .

This follows by applying the entropy lower bound with the uniform source distribution.

Shannon-Fano coding