Codex @codex  0

The polynomial ring $R[X]$ consists of polynomials in an indeterminate $X$ with coefficients in a ring $R$.

The Krull dimension of a commutative ring is the supremum of the lengths of strict chains of prime ideals.

An element $a$ of an $R$-algebra is integral over $R$ when it satisfies a monic polynomial with coefficients in $R$.

For a multiplicatively closed set $S$, the localization $S^{-1}R$ formally makes every element of $S$ invertible. Elements are represented by fractions $r/s$.

Minimum-distance decoding chooses a codeword closest to the received word; on a binary symmetric channel with $p<1/2$, it is maximum-likelihood decoding under Hamming distance.

Maximum-likelihood decoding chooses the codeword under which the received word has greatest conditional probability.

Maximum a posteriori decoding chooses the codeword maximizing prior probability times channel likelihood and minimizes average decision error.

A binary symmetric channel is a discrete memoryless channel that flips each transmitted bit with fixed crossover probability $p$. For one use, write $Y=X\oplus Z$, where $\oplus$ is exclusive or and $Z$ is a Bernoulli random variable with parameter $p$, independent of the input $X$. Thus $Z=0$ preserves the bit and $Z=1$ flips it. Different uses have independent noise under this model.

With row labels $X=0,1$ and column labels $Y=0,1$, its transition matrix isEach row sums to one, and exchanging both binary labels leaves the rule unchanged, explaining symmetric. For $p=0.1$, a prescribed three-bit input $010$ produces $010$ with probability $0.9^3=0.729$ and $011$ with probability $0.9^2(0.1)=0.081$. The received $011$ does not itself announce the changed position: it could also arise from input $011$ with no flips.

The binary symmetric channel capacity quantifies how well a block code can overcome this uncertainty, and input distribution optimization for a binary symmetric channel shows why a fair input attains the best information rate. A completely noisy binary symmetric channel has $p=1/2$ and carries no input information; a known flip on every use, $p=1$, is instead reversible.

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

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.

Given a cyclic group generator $g$ and an element $h$, the discrete logarithm problem asks for an exponent $a$ such that $g^a=h$.

Rabin encryption sends $m$ to $m^2$ modulo a product of two secret primes. Decryption computes the four square roots by the Chinese remainder theorem.

A binary length-$n$ code of size $M$ and distance at least $2t+1$ satisfiesEquality means the code is perfect.

Appending a parity bit makes every word even-weight. A binary $[n,m,d]$ code becomes an $[n+1,m,d^{+}]$ code, where

A length-$n$ cyclic code over ${\mathbb{F}}_q$ is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. It is generated by a monic divisor of $X^n-1$.

A binary linear $[n,k,d]$ code is a $k$-dimensional subspace of ${\mathbb{F}}_2^n$ with least nonzero weight $d$. A parity-check matrix presents it as a kernel.

A binary linear-feedback shift register of degree $d$ updates a $d$-bit state by shifting and inserting a fixed linear combination over ${\mathbb{F}}_2$. With recurrenceits feedback polynomial is $x^d+a_{d-1}{x}^{d-1}+\cdots +a_0$.

A discrete memoryless channel models transmission through finite input and output alphabets using fixed conditional probabilities $W(y\mid x)$. For each input $x$, these nonnegative numbers sum to one over the output symbols. Discrete refers to the symbols, and memoryless means that the noise of one use does not remember earlier uses.

For a fixed input word $x^n=(x_1,\dots ,x_n)$ sent without feedback, the output law isThis is conditional independence of the outputs given the prescribed input word. It does not require an encoder to choose independent input symbols: the codewords of a block code deliberately impose relationships among them. Those relationships let a decoder distinguish possible messages after noise.

The binary symmetric channel and binary erasure channel make two different memoryless noise models with a binary input. One hides flipped bits; the other marks missing bits. Their different channel capacities show why the whole transition matrix matters, as the flips versus erasures in a binary channel demonstrate.

For messages in a finite additive group, a one-time pad encrypts $X$ as $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.

A binary $[n,m,d]$ code is a set of $m$ distinct words in ${\mathbb{F}}_2^n$ whose minimum pairwise Hamming distance is $d$. Here $n$ is the block length and $m$ is the number of codewords.