Shannon's coding theorems form the twin pillars of information theory. The source coding theorem (1948) establishes that data can be compressed to an average code length no shorter than the entropy of the source, while the channel coding theorem guarantees reliable communication at rates up to channel capacity. Together, these theorems define the fundamental limits of information processing and have inspired influential models of neural coding and cognitive representation.
Source Coding
L* ≥ H(X) for any uniquely decodable code
Huffman coding achieves: H(X) ≤ L_Huffman < H(X) + 1
H(X) = −Σ p(xᵢ) · log₂ p(xᵢ)
Source coding (data compression) assigns shorter codewords to more probable symbols and longer codewords to less probable symbols. Shannon proved that no uniquely decodable code can have an average length less than the source entropy H(X). Huffman (1952) provided an algorithm for constructing optimal prefix-free codes that come within one bit of the entropy bound. Shannon-Fano-Elias coding and arithmetic coding can approach the entropy bound even more closely for long sequences.
Channel Coding
Channel coding adds structured redundancy to messages so that errors introduced by the channel can be detected and corrected. Shannon proved that for any rate R below channel capacity C, codes exist that achieve arbitrarily low error probability. This seemingly paradoxical result — that redundancy can simultaneously allow both compression and error correction — was revolutionary. Practical error-correcting codes, from Hamming codes to turbo codes and low-density parity-check codes, have progressively approached Shannon's theoretical limits.
The nervous system faces a problem analogous to source coding: representing the high-dimensional sensory world using a limited number of neurons and spikes. Barlow (1961) proposed that sensory neurons implement efficient coding by reducing redundancy in neural representations, analogous to compression. Laughlin (1981) showed that the contrast-response function of fly photoreceptors matches the transformation predicted by histogram equalization — an optimal source code for maximizing information about natural scenes given the neuron's limited dynamic range.
Applications to Cognitive Science
Coding theory has influenced cognitive science in several ways. The concept of "chunking" (Miller, 1956) can be understood as a recoding operation that groups items into higher-order units, effectively compressing information and expanding the apparent capacity of working memory. In language processing, speakers tend toward efficient coding: more predictable words are shorter (Zipf's law) and are articulated more rapidly, consistent with a communication system optimized near the source coding bound.
In neural population coding, the question of how populations of neurons represent information can be framed in coding-theoretic terms. Rate codes, temporal codes, and population codes correspond to different encoding strategies with different capacity-complexity tradeoffs. The study of neural codes continues to draw on Shannon's framework to ask how efficiently the brain represents and transmits information.