Coding theory Created 2026-09-24 Updated 2026-10-18
Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.
The simplest error-correction example sends as and as . If the receiver sees , at most one bit flip is consistent with , whereas two flips would be needed to obtain it from . A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.
The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.
Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.[ref]
https://zoo.cs.yale.edu/classes/cs323/doc/Hamming.pdf. Hamming, Error Detecting and Error Correcting Codes, 1950
Coordinate revealment 2026-10-14
The coordinate revealment of coordinate for a decision tree under input probability distribution isIt depends on the chosen decision tree and the probability distribution, not just on the Boolean function. Since no coordinate is queried twice on a graph path, indicator functions giveThe second equality uses linearity of expectation; it does not require independence of random variables or a product measure. The cited paper defines these inspection probabilities and their sum for product measures; the displayed indicator function argument extends the identity to any input probability distribution.[ref]
For the three-bit majority decision tree under the discrete uniform distribution, , whose sum is . Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same majority function, depth and expected query cost, but coordinate revealments . The asymmetry belongs to the chosen query order. Parity gives for every exact decision tree without repeated queries. If repeated queries were charged, inspection probabilities would count distinct coordinates; total query count would instead require expected multiplicities.
Decision-tree query cost 2026-10-14
For a particular decision tree , its decision-tree query cost is the number of queries along the graph path followed by input . Its actual tree depth isThe query vertices count as operations; each is followed by one answer edge. Thus a leaf reached after queries has graph path length , and a tree consisting only of an output leaf has depth zero. With no repeated coordinates, . The decision-tree depth minimizes over all correct decision trees for ; measures the chosen algorithm, while measures the Boolean function.
Choose an input probability distribution and let have that distribution. Then is a random variable even when the decision tree is deterministic. Its probability mass function describes how often each path length occurs, and its expected value is the expected query cost. None of these quantities changes the actual maximum depth of .
Uniform three-bit inputs: query-count distributions and coordinate revealment for majority and parity
. Details. The left panel aggregates the eight inputs from the three-bit majority decision tree: four cost two queries and four cost three. Parity always costs three. The right panel asks a different question, which coordinates are inspected: the majority function algorithm always queries coordinates 1 and 2, but queries coordinate 3 only on disagreements. These are probabilities of inspection, not probabilities that a bit equals one.
Digital smoother 2026-10-31
A sampled Boolean circuit that suppresses short input changes using recent samples. A three-sample majority function removes isolated one-sample changes; a stateful variant updates its stored output only after three equal input samples. These are different specifications.
Exact two-query majority algorithm 2026-10-07
One exact parity query determines whether the first two bits agree. If they agree, a second query reads one of them; otherwise it reads the third bit. Those values respectively determine the three-bit majority function. The matching lower bound follows from its degree-three multilinear polynomial.
Expected query cost 2026-10-14
For a fixed decision tree and input probability distribution , its expected query cost isUnder the discrete uniform distribution on the eight three-bit inputs, the three-bit majority decision tree hasThis is an exact average, not a fractional query made during one execution. It is also optimal among exact deterministic decision trees under this discrete uniform distribution: one observed bit never determines the majority function; whichever two distinct coordinates are inspected first, their values disagree with probability , forcing a third query. In comparison, querying all three bits unconditionally has the same actual depth three but expected query cost three.
For an arbitrary input probability distribution, the same fixed three-bit majority decision tree gives . For three independent random variables, each a Bernoulli random variable with common one-probability , this becomes ; the value depends on . Averaging over inputs should also be distinguished from averaging over an algorithm's internal random choices at a fixed input.[ref]
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 67 2 b Solution Created 2026-10-03 Updated 2026-10-07
For the three-bit majority function, the pair products count how many pairs of input bits are both one. Their sum is zero at Hamming weights zero and one, one at weight two, and three at weight three. Subtracting twice the triple product corrects the last value. HenceThis is a multilinear polynomial of degree three, and its top coefficient is nonzero. Uniqueness of the Boolean multilinear polynomial excludes a degree-two alternative. The polynomial method for quantum query lower bounds therefore yields , and the integer number of queries gives
Use two history D flip-flops. Write , and for the signals just before the active clock edge; update the history by and . Two or more of the three samples are one exactly when some pair are both one, so the majority function isThree two-input AND gates and one three-input OR gate implement this disjunctive normal form. If a registered output is wanted, feed the expression to the D input of another D flip-flop and capture it at the same edge as the history update. All right-hand sides use the pre-edge values, so no extra sample of delay is introduced.
The three terms are necessary in a minimal sum of products: the input triples , and must each be covered, and a single product covering two of them would also cover a triple having only one one. Thus the minimum is three products, each with two Boolean literals.
Sample history and registered output for the three digital smoother designs
. Details. Repetition code Created 2026-10-03 Updated 2026-11-05
A binary repetition code represents one bit by repeating it times, using codewords and . Their Hamming distance is , and the code rate is . For odd , the majority function recovers the input whenever fewer than half the positions have flipped. Even allows a tied vote, so a decoder must specify how it handles that case.
For , the received words decode to zero; decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.
If each position passes independently through a binary symmetric channel with crossover probability , a decoded error requires at least two flips. The binomial distribution givesAt , the uncoded error probability is , while the three-bit code's decoded error probability is . This improvement costs three transmitted bits per message bit. For , ; for , one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.
Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability , repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.
Three-bit majority decision tree Created 2026-10-14 Updated 2026-10-20
Three votes give a small but revealing majority function:Our decision tree queries , then . If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.
Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost , and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.
All eight inputs give the following exhaustive check. The parity column is the parity of , computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.
The worst inputs for this decision tree are , exactly those with . Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is , even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.



