Hubbry Logo
Convolutional codeConvolutional codeMain
Open search
Convolutional code
Community hub
Convolutional code
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Convolutional code
Convolutional code
Convolutional code
View on Wikipedia
from Wikipedia

In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time-variant trellis and therefore are typically hard-decision decoded. Convolutional codes are often characterized by the base code rate and the depth (or memory) of the encoder . The base code rate is typically given as , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length" K, where the output is a function of the current input as well as the previous inputs. The depth may also be given as the number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically: ).

Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real-world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes, which generally have fixed block lengths that are determined by algebraic properties.

The code rate of a convolutional code is commonly modified via symbol puncturing. For example, a convolutional code with a 'mother' code rate may be punctured to a higher rate of, for example, simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.

History

[edit]

Convolutional codes were introduced in 1955 by Peter Elias. It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967, Andrew Viterbi determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders — the Viterbi algorithm. Other trellis-based decoder algorithms were later developed, including the BCJR decoding algorithm.

Recursive systematic convolutional codes were invented by Claude Berrou around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as turbo codes.[1]

Using the "convolutional" terminology, a classic convolutional code might be considered a Finite impulse response (FIR) filter, while a recursive convolutional code might be considered an Infinite impulse response (IIR) filter.

Where convolutional codes are used

[edit]
Stages of channel coding in GSM.[2] Block encoder and Parity check – error detection part. Convolutional encoder and Viterbi decoder – error correction part. Interleaving and Deinterleaving – code words separation increasing in time domain and to avoid bursty distortions.

Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as digital video, radio, mobile communications (e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7)[3][4]) and satellite communications.[5] These codes are often implemented in concatenation with a hard-decision code, particularly Reed–Solomon. Prior to turbo codes such constructions were the most efficient, coming closest to the Shannon limit.

Convolutional encoding

[edit]

To convolutionally encode data, start with k memory registers, each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has n modulo-2 adders (a modulo 2 adder can be implemented with a single Boolean XOR gate, where the logic is: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), and n generator polynomials — one for each adder (see figure below). An input bit m1 is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs n symbols. These symbols may be transmitted or punctured depending on the desired code rate. Now bit shift all register values to the right (m1 moves to m0, m0 moves to m−1) and wait for the next input bit. If there are no remaining input bits, the encoder continues shifting until all registers have returned to the zero state (flush bit termination).

Img.1. Rate 1/3 non-recursive, non-systematic convolutional encoder with constraint length 3

The figure below is a rate 1⁄3 (m⁄n) encoder with constraint length (k) of 3. Generator polynomials are G1 = (1,1,1), G2 = (0,1,1), and G3 = (1,0,1). Therefore, output bits are calculated (modulo 2) as follows:

n1 = m1 + m0 + m−1
n2 = m0 + m−1
n3 = m1 + m−1.

Convolutional codes can be systematic and non-systematic:

  • systematic repeats the structure of the message before encoding
  • non-systematic changes the initial structure

Non-systematic convolutional codes are more popular due to better noise immunity. It relates to the free distance of the convolutional code.[6]

  • A short illustration of non-systematic convolutional code.
    A short illustration of non-systematic convolutional code.
  • A short illustration of systematic convolutional code.
    A short illustration of systematic convolutional code.

Recursive and non-recursive codes

[edit]

The encoder on the picture above is a non-recursive encoder. Here's an example of a recursive one and as such it admits a feedback structure:

Img.2. Rate 1/2 8-state recursive systematic convolutional encoder. Used as constituent code in 3GPP 25.212 Turbo Code.

The example encoder is systematic because the input data is also used in the output symbols (Output 2). Codes with output symbols that do not include the input data are called non-systematic.

Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn't a strict requirement, but a common practice.

The example encoder in Img. 2. is an 8-state encoder because the 3 registers will create 8 possible encoder states (23). A corresponding decoder trellis will typically use 8 states as well.

Recursive systematic convolutional (RSC) codes have become more popular due to their use in Turbo Codes. Recursive systematic codes are also referred to as pseudo-systematic codes.

Other RSC codes and example applications include:

Img. 3. Two-state recursive systematic convolutional (RSC) code. Also called an 'accumulator.'

Useful for LDPC code implementation and as inner constituent code for serial concatenated convolutional codes (SCCC's).

Img. 4. Four-state recursive systematic convolutional (RSC) code.

Useful for SCCC's and multidimensional turbo codes.

Img. 5. Sixteen-state recursive systematic convolutional (RSC) code.

Useful as constituent code in low error rate turbo codes for applications such as satellite links. Also suitable as SCCC outer code.

Impulse response, transfer function, and constraint length

[edit]

A convolutional encoder is called so because it performs a convolution of the input stream with the encoder's impulse responses:

where x is an input sequence, yj is a sequence from output j, hj is an impulse response for output j and denotes convolution.

A convolutional encoder is a discrete linear time-invariant system. Every output of an encoder can be described by its own transfer function, which is closely related to the generator polynomial. An impulse response is connected with a transfer function through Z-transform.

Transfer functions for the first (non-recursive) encoder are:

Transfer functions for the second (recursive) encoder are:

Define m by

where, for any rational function ,

.

Then m is the maximum of the polynomial degrees of the

, and the constraint length is defined as . For instance, in the first example the constraint length is 3, and in the second the constraint length is 4.

Trellis diagram

[edit]
See also: Trellis (graph) and Trellis coded modulation

A convolutional encoder is a finite state machine. An encoder with n binary cells will have 2n states.

Imagine that the encoder (shown on Img.1, above) has '1' in the left memory cell (m0), and '0' in the right one (m−1). (m1 is not really a memory cell because it represents a current value). We will designate such a state as "10". According to an input bit the encoder at the next turn can convert either to the "01" state or the "11" state. One can see that not all transitions are possible for (e.g., a decoder can't convert from "10" state to "00" or even stay in "10" state).

All possible transitions can be shown as below:

Img.6. A trellis diagram for the encoder on Img.1. A path through the trellis is shown as a red line. The solid lines indicate transitions where a "0" is input and the dashed lines where a "1" is input.

An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example.

This diagram gives us an idea about decoding: if a received sequence doesn't fit this graph, then it was received with errors, and we must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea.

Free distance and error distribution

[edit]
Theoretical bit-error rate curves of encoded QPSK (recursive and non-recursive, soft decision), additive white Gaussian noise channel. Curves are small distinguished due to approximately the same free distances and weights.

The free distance[7] (d) is the minimal Hamming distance between different encoded sequences. The correcting capability (t) of a convolutional code is the number of errors that can be corrected by the code. It can be calculated as

Since a convolutional code doesn't use blocks, processing instead a continuous bitstream, the value of t applies to a quantity of errors located relatively near to each other. That is, multiple groups of t errors can usually be fixed when they are relatively far apart.

Free distance can be interpreted as the minimal length of an erroneous "burst" at the output of a convolutional decoder. The fact that errors appear as "bursts" should be accounted for when designing a concatenated code with an inner convolutional code. The popular solution for this problem is to interleave data before convolutional encoding, so that the outer block (usually Reed–Solomon) code can correct most of the errors.

Decoding convolutional codes

[edit]
See also: Viterbi algorithm
Bit error ratio curves for convolutional codes with different options of digital modulations (QPSK, 8-PSK, 16-QAM, 64-QAM) and LLR Algorithms.[8][9] (Exact[10] and Approximate[11]) over additive white Gaussian noise channel.

Several algorithms exist for decoding convolutional codes. For relatively small values of k, the Viterbi algorithm is universally used as it provides maximum likelihood performance and is highly parallelizable. Viterbi decoders are thus easy to implement in VLSI hardware and in software on CPUs with SIMD instruction sets.

Longer constraint length codes are more practically decoded with any of several sequential decoding algorithms, of which the Fano algorithm is the best known. Unlike Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing the use of strong, long-constraint-length codes. Such codes were used in the Pioneer program of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large Reed–Solomon error correction codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates.

Both Viterbi and sequential decoding algorithms return hard decisions: the bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the Soft output Viterbi algorithm. Maximum a posteriori (MAP) soft decisions for each bit can be obtained by use of the BCJR algorithm.

[edit]
Shift-register for the (7, [171, 133]) convolutional code polynomial. Branches: , . All of the math operations should be done by modulo 2.
Theoretical bit-error rate curves of encoded QPSK (soft decision), additive white Gaussian noise channel. Longer constraint lengths produce more powerful codes, but the complexity of the Viterbi algorithm increases exponentially with constraint lengths, limiting these more powerful codes to deep space missions where the extra performance is easily worth the increased decoder complexity.

In fact, predefined convolutional codes structures obtained during scientific researches are used in the industry. This relates to the possibility to select catastrophic convolutional codes (causes larger number of errors).

An especially popular Viterbi-decoded convolutional code, used at least since the Voyager program, has a constraint length K of 7 and a rate r of 1/2.[12]

Mars Pathfinder, Mars Exploration Rover and the Cassini probe to Saturn use a K of 15 and a rate of 1/6; this code performs about 2 dB better than the simpler code at a cost of 256× in decoding complexity (compared to Voyager mission codes).

The convolutional code with a constraint length of 2 and a rate of 1/2 is used in GSM as an error correction technique.[13]

Punctured convolutional codes

[edit]
See also: Punctured code
Convolutional codes with 1/2 and 3/4 code rates (and constraint length 7, Soft decision, 4-QAM / QPSK / OQPSK).[14]

Convolutional code with any code rate can be designed based on polynomial selection;[15] however, in practice, a puncturing procedure is often used to achieve the required code rate. Puncturing is a technique used to make a m/n rate code from a "basic" low-rate (e.g., 1/n) code. It is achieved by deleting of some bits in the encoder output. Bits are deleted according to a puncturing matrix. The following puncturing matrices are the most frequently used:

Code rate Puncturing matrix Free distance (for NASA standard K=7 convolutional code)
1/2
(No perf.)
1
1
10
2/3
1 0
1 1
6
3/4
1 0 1
1 1 0
5
5/6
1 0 1 0 1
1 1 0 1 0
4
7/8
1 0 0 0 1 0 1
1 1 1 1 0 1 0
3

For example, if we want to make a code with rate 2/3 using the appropriate matrix from the above table, we should take a basic encoder output and transmit every first bit from the first branch and every bit from the second one. The specific order of transmission is defined by the respective communication standard.

Punctured convolutional codes are widely used in the satellite communications, for example, in Intelsat systems and Digital Video Broadcasting.

Punctured convolutional codes are also called "perforated".

Turbo codes: replacing convolutional codes

[edit]
Main article: Turbo code
A turbo code with component codes 13, 15.[16] Turbo codes get their name because the decoder uses feedback, like a turbo engine. Permutation means the same as the interleaving. C1 and C2 are recursive convolutional codes. Recursive and non-recursive convolutional codes are not so much different in BER performance, however, recursive type of is implemented in Turbo convolutional codes due to better interleaving properties.[17]

Simple Viterbi-decoded convolutional codes are now giving way to turbo codes, a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by Shannon's theorem with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. Concatenation with an outer algebraic code (e.g., Reed–Solomon) addresses the issue of error floors inherent to turbo code designs.

See also

[edit]

References

[edit]
[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Convolutional code

View on Grokipedia
from Grokipedia
A convolutional code is a type of error-correcting code used in digital communications to add to a , enabling the detection and correction of transmission errors in noisy channels. Unlike , which process data in fixed-length segments, convolutional codes encode the input continuously using a linear finite-state that combines current and previous input bits through modulo-2 addition, typically producing output symbols at a rate of k/n where k is the number of input bits and n is the number of output bits per step, with the code's memory defined by its constraint length K (or ν). This structure generates infinite-length code sequences that can be terminated to form finite blocks, making them particularly effective for power-limited environments and burst error correction. Convolutional codes were first introduced by Peter Elias in 1955 as an alternative to traditional , aiming to approach with low error probability through continuous encoding rather than discrete blocks. Elias's seminal work, "Coding for Noisy Channels," described the basic encoder using parity-check symbols derived from convolutional operations, laying the foundation for their use in . The codes are typically binary and linear time-invariant for simplicity, represented by generator polynomials that define the connections in the , with the free distance d_free serving as a key measure of error-correcting capability—higher values indicate better performance against errors. Optimal codes, such as rate-1/2 designs with constraint length 7 (yielding d_free=10), provide coding gains of around 5 dB in channels. Decoding of convolutional codes is commonly achieved through the , a maximum-likelihood method introduced by Andrew J. Viterbi in 1967, which efficiently searches the trellis diagram of possible code paths using dynamic programming to minimize proportional to the number of states (2^{K-1}). This algorithm has asymptotic optimality and is practical for real-time applications, though it can be extended with soft-decision inputs for improved performance. In practice, convolutional codes are often punctured to achieve higher rates or concatenated with other codes like Reed-Solomon for enhanced robustness, as seen in standards such as NASA's deep space missions and the European Space Agency's telemetry systems. Due to their adaptability to streaming data and effectiveness in low-signal-to-noise ratio scenarios, convolutional codes have been integral to modern communications, including satellite links, wireless networks (e.g., CDMA and GSM cellular systems), and voice-band modems, where they enable reliable transmission over fading channels and interference. They continue to influence emerging technologies like vehicular-to-everything (V2X) communications and underwater acoustics, often hybridized with turbo or low-density parity-check codes for near-Shannon-limit performance.

Historical Development

Origins and Invention

Convolutional codes were invented by Peter Elias in 1955 at the Massachusetts Institute of Technology (MIT), where he was a faculty member working on advanced error-correcting techniques as part of broader research into sequential codes. In his influential paper "Coding for Noisy Channels," Elias proposed these codes to enable reliable communication over noisy channels at rates approaching the theoretical limits established by . The development of convolutional codes was deeply motivated by Claude Shannon's 1948 noisy channel coding theorem, which demonstrated the existence of codes capable of achieving arbitrarily low error probabilities at rates up to the , but did not provide explicit constructions. Elias sought to bridge this gap by exploring continuous encoding methods that could handle streaming data, unlike the discrete block-based approaches dominant in early , thereby facilitating practical implementations for real-time transmission scenarios. Elias initially described convolutional codes as linear time-varying codes with effectively infinite length, distinguishing them from fixed-length by allowing the encoding process to incorporate across an unbounded sequence of symbols. This structure enabled the generation of parity-check symbols through a convolutional operation, providing a flexible framework for error correction in continuous data flows. Early practical considerations for real-time error correction in data transmission emerged in the late at MIT's Lincoln Laboratory, where simulations and hardware prototypes laid the groundwork for deployable systems. These efforts paved the way for later adoption in space communications.

Key Milestones and Adoption

The foundational work on convolutional code decoding was advanced by in 1967, who established error bounds and introduced an asymptotically optimal maximum-likelihood decoding algorithm that became essential for practical implementation, although further refinements followed in subsequent years. In the , convolutional codes achieved their first major practical adoption through NASA's deep-space missions, notably employing a rate-1/2 code in the for data transmission over noisy interplanetary channels. This application demonstrated the codes' robustness in extreme environments, paving the way for broader use in space communications. By the 1970s, integration into military systems accelerated reliability in secure links, as seen in standards like for tactical radios, while early cellular prototypes explored their potential for mobile voice error correction. The 1980s and 1990s marked widespread commercialization and standardization. GSM networks adopted a rate-1/2 convolutional code with constraint length k=5 to protect speech and signaling data against and interference, enabling reliable global mobile service rollout starting in 1991. Concurrently, satellite applications proliferated, with GPS incorporating convolutional coding in its L1 C/A signal for navigation message integrity against atmospheric distortions. A pivotal 1993 publication on Viterbi decoding optimizations further refined computational efficiency, directly shaping CCSDS recommendations for concatenated coding in space standards.

Overview and Fundamentals

Definition and Basic Principles

Convolutional codes constitute a class of error-correcting codes designed for digital communication systems, where each output symbol is generated as a of a fixed number of consecutive input bits, referred to as a sliding window, thereby producing a continuous stream of encoded bits in contrast to the fixed-block structure of . This approach enables ongoing encoding without predefined message boundaries, making convolutional codes particularly suitable for streaming data transmission over noisy channels. At their core, convolutional codes operate as linear time-invariant filters over the binary field GF(2), where the encoded output sequence is obtained by convolving the input bit sequence with a set of generator sequences that define the code's structure. Theoretically, this implies an , as each input bit influences all subsequent outputs; however, practical implementations impose a finite constraint to bound and ensure realizability with finite-state machines. The over GF(2) ensures that the holds, allowing efficient decoding techniques based on algebraic properties. A fundamental parameter of convolutional codes is the memory order mm, which specifies the number of previous input bits retained in the encoder's , leading to 2m2^m distinct internal states that track the memory contents at any encoding step. The rate R=k/nR = k/n quantifies the , indicating that kk input bits are mapped to nn output bits per encoding step, with typical values like R=1/2R = 1/2 providing for correction at the cost of increased bandwidth. For illustration, consider a rate-1/2 with m=2m=2: processing the input 10 (followed by two zero tail bits for termination) yields the output 11 01 11 00, where each pair of output bits depends on the current input bit and the two prior bits stored in .

Comparison to Other Error-Correcting Codes

Convolutional codes differ fundamentally from , such as Hamming and Reed-Solomon codes, in their encoding mechanism. operate on fixed-length input blocks to produce corresponding output codewords, relying on algebraic structures like parity-check matrices or polynomials defined over finite fields. In contrast, convolutional codes encode an input continuously through a linear shift-register structure, where each output symbol depends not only on the current input but also on previous inputs via the code's , enabling ongoing processing without discrete block boundaries. This distinction makes convolutional codes more adaptable to streaming or variable-length data scenarios, whereas necessitate buffering data into predefined blocks, which can introduce delays in continuous transmission systems. A primary advantage of convolutional codes lies in their suitability for real-time and streaming applications, where the sequential nature of encoding and decoding allows for variable latency that aligns with ongoing arrival, unlike the fixed-block of codes like Hamming, which may require complete block reception before correction. This flexibility is particularly beneficial in systems with large or indefinite , such as communications, where convolutional codes demonstrate superior energy efficiency and performance as block lengths or delays increase compared to traditional . Moreover, convolutional codes are frequently integrated into hybrid error-correction schemes, where they serve as inner codes concatenated with outer like Reed-Solomon; this combination exploits the burst-error resilience of Reed-Solomon with the random-error correction prowess of convolutional codes, enhancing overall system reliability in concatenated architectures. Despite these strengths, convolutional codes have notable limitations relative to advanced block codes, particularly low-density parity-check (LDPC) codes. At low code rates, LDPC block codes generally outperform convolutional codes by approaching more closely, achieving higher coding gains with lower error floors due to their sparse parity-check matrices and iterative message-passing decoding. Convolutional codes also exhibit greater sensitivity to burst errors, as their finite can propagate error bursts across the trellis; without additional interleaving to disperse errors into random patterns, their performance degrades significantly in bursty channels, in contrast to Reed-Solomon codes, which inherently correct bursts up to a designed without interleaving. In terms of , a standard rate-1/2 convolutional code with Viterbi decoding provides an asymptotic coding gain of approximately 5 dB at a (BER) of 10−510^{-5} compared to uncoded transmission over an channel, highlighting their effectiveness for moderate-rate applications, though gains diminish at very low rates relative to LDPC alternatives.

Applications

Communication Systems and Protocols

Convolutional codes play a crucial role in wireless communication systems, particularly in legacy cellular standards for protecting voice channels against errors in fading environments. In the Global System for Mobile Communications (GSM), the voice channels employ a rate-1/2 convolutional code with constraint length 7, defined by generator polynomials 133 and 171 in octal notation, to encode class 1 bits of the speech data, ensuring reliable transmission over noisy radio links. Similarly, in Universal Mobile Telecommunications System (UMTS), convolutional coding with rates of 1/2 or 1/3 and constraint length 9—using generator polynomials 561 and 753 (octal) for rate 1/2, and 557, 663, 711 (octal) for rate 1/3—is applied to voice and control channels for forward error correction, enhancing speech quality in wideband code-division multiple access (W-CDMA) setups. Early versions of the IEEE 802.11 Wi-Fi standards, such as 802.11a and 802.11g, integrate rate-1/2 convolutional codes with constraint length 7 and the same 133/171 generator polynomials at the physical layer to provide forward error correction for orthogonal frequency-division multiplexing (OFDM) signals, improving throughput in local area networks. In and deep communications, convolutional codes are essential for mitigating signal and over vast distances. The (DSN) utilizes rate-1/2 convolutional codes with constraint length 7 for downlink, enabling robust data recovery from distant probes. This configuration was notably employed in the Voyager missions, where the convolutional encoder processes high-rate data streams with a symbol rate twice the bit rate, concatenated with outer Reed-Solomon codes to achieve low bit error rates in the challenging interplanetary channel. For wired , convolutional codes provide error protection in environments susceptible to impulse and . Digital subscriber line (DSL) modems, particularly asymmetric DSL (), incorporate convolutional codes as the inner layer of a concatenated scheme, often decoded via the , to correct random errors in multicarrier-modulated signals transmitted over twisted-pair lines. Integrated Services Digital Network (ISDN) systems similarly leverage convolutional-based trellis coding for error resilience in basic rate interfaces, safeguarding voice and data services against channel impairments in access networks. A key protocol standardizing convolutional code usage is the Consultative Committee for Space Data Systems (CCSDS) TM Synchronization and Channel Coding recommendation (CCSDS 131.0-B), which mandates convolutional coding—typically rate-1/2 with constraint length 7—as the inner code in a concatenated with an outer Reed-Solomon code (255,223) for applications, ensuring interoperability across space agencies for burst-error-prone links.

Modern and Emerging Uses

In fifth-generation () New Radio (NR) systems, convolutional codes have been proposed in hybrid schemes with low-density parity-check (LDPC) codes for ultra-reliable low-latency communication (URLLC) scenarios, integrating sequential error correction with iterative decoding to achieve reliability targets below 10^{-5} packet rate under stringent latency constraints of 1 ms. Such hybrids address the challenges of short codewords in industrial IoT and vehicular applications by optimizing error floors and convergence in decoding. In (IoT) networks, lightweight convolutional code variants are employed in low-power protocols to enhance reliability in battery-constrained environments. (BLE), as defined in the Bluetooth Core Specification version 5.0 and later, incorporates rate-1/3 convolutional (FEC) in its LE Coded PHY mode, operating at 500 kbps or 125 kbps to extend range and robustness against interference while minimizing computational overhead. This non-systematic, non-recursive code with constraint length 4 uses generator polynomials (7, 5, 7 in octal) to protect payload data, enabling error rates below 10^{-3} in fading channels typical of wearable and devices. For Zigbee-based systems adhering to , convolutional coding has been proposed as a variant to improve transceiver performance in mesh networks, with rate-1/8 codes demonstrating up to 3 dB coding gain over uncoded schemes in simulations for energy-efficient . These adaptations prioritize Viterbi decoding complexity under 10^4 operations per frame to preserve battery life exceeding 5 years in typical deployments. Convolutional codes are integrated into (QKD) protocols for error correction in noisy quantum channels, where quantum convolutional codes provide continuous protection for streams without requiring block synchronization. These codes, constructed via stabilizer formalism on infinite lattices, correct phase and bit-flip s in continuous-variable QKD systems. In optical communications, convolutional codes enhance in fiber-optic systems, particularly when paired with multilevel modulation schemes like 16-QAM, yielding bit rates below 10^{-9} at signal-to-noise ratios 2-3 dB below uncoded thresholds in long-haul terrestrial links. Rate-1/2 non-systematic convolutional encoders with Viterbi decoding are favored for their adaptability to soft-decision inputs from coherent receivers, supporting data rates up to 100 Gbps in dense (DWDM) setups. Convolutional codes continue to be explored for real-time video streaming applications, providing error resilience in unreliable links using punctured rate-1/2 variants to add . In hybrid configurations, convolutional encoding precedes video codecs to provide burst-error correction for low-latency applications such as , where decoding latency is constrained to under 20 ms on resource-limited edge nodes. This stems from the codes' efficient hardware implementation on field-programmable gate arrays, suitable for scenarios with variable channel conditions. As of 2025, convolutional codes are also proposed in research for massive IoT and concatenated with polar/LDPC codes in updated space data systems like CCSDS for enhanced IoT reliability.

Encoding Process

Generator Polynomials and Shift Registers

The encoder for a convolutional code is typically implemented using a architecture with m elements, where m = K - 1 and K is the constraint length. This structure functions as a (LFSR), where each new input bit enters the register and causes the existing contents to shift, typically to the right. Specific positions in the register, known as taps—including the current input and selected elements—are connected to modulo-2 adders (XOR gates) to produce the output bits according to the generator polynomials. This setup ensures that the output depends on the current input and the previous m input bits stored in . Generator polynomials specify the tap connections and are binary polynomials over GF(2), often represented in octal notation for compactness. For a rate-1/n code, there are n such polynomials, denoted g^{(i)}(D) for i = 1 to n, where D represents the delay operator. The overall encoder is described by the generator matrix in polynomial form G(D) = [g^{(1)}(D) \ g^{(2)}(D) \ \dots \ g^{(n)}(D)]. A widely adopted example is the rate-1/2 code with constraint length K=7, known as the NASA standard for deep-space communications, using g^{(1)}(D) = 1 + D^3 + D^4 + D^5 + D^6 (octal 171) and g^{(2)}(D) = 1 + D + D^3 + D^4 + D^6 (octal 133). These polynomials correspond to binary representations 1111001 and 1011011, respectively, where the least significant bit is the coefficient of D^0 (current input) and the most significant bit is for D^6 (oldest memory). The outputs are computed via convolution of the input sequence with each generator polynomial, modulo 2. In the time domain, for input sequence {u_j} (with u_j = 0 for j < 0), the i-th output bit at time j is \begin{equation*} v_j^{(i)} = \sum_{l=0}^{m} u_{j-l} , g_l^{(i)} \pmod{2}, \quad i = 1, \dots, n. \end{equation*} This equation captures the linear combination of the current and past inputs weighted by the polynomial coefficients g_l^{(i)}. For the rate-1/2, K=7 code with polynomials (171, 133)_8, the encoding of input 101 (with initial register state all zeros) proceeds as follows, using the coefficients g_l^{(1)} = [1, 0, 0, 1, 1, 1, 1] and g_l^{(2)} = [1, 1, 0, 1, 1, 0, 1] (l = 0 to 6). At each step, the register holds the last 6 inputs, and outputs are XOR sums over the taps.
Step (j)Input u_jRegister state after shift (u_j, u_{j-1}, ..., u_{j-6})v_j^{(1)} calculation (sum mod 2)v_j^{(2)} calculation (sum mod 2)Output (v_j^{(1)} v_j^{(2)})
011 0 0 0 0 0 01·1 + 0·0 + 0·0 + 1·0 + 1·0 + 1·0 + 1·0 = 11·1 + 1·0 + 0·0 + 1·0 + 1·0 + 0·0 + 1·0 = 111
100 1 0 0 0 0 01·0 + 0·1 + 0·0 + 1·0 + 1·0 + 1·0 + 1·0 = 01·0 + 1·1 + 0·0 + 1·0 + 1·0 + 0·0 + 1·0 = 101
211 0 1 0 0 0 01·1 + 0·0 + 0·1 + 1·0 + 1·0 + 1·0 + 1·0 = 11·1 + 1·0 + 0·1 + 1·0 + 1·0 + 0·0 + 1·0 = 111
The resulting output sequence is 110111, demonstrating how the code introduces redundancy based on the memory of prior inputs. To fully terminate the code and return to the zero state, additional zero inputs equal to m would be appended, but this example focuses on the core generation process.

Systematic vs. Non-Systematic Encoding

In non-systematic convolutional encoding, all output bits are generated as linear combinations of the current and past input bits stored in shift registers, without directly reproducing the input sequence in any output stream. This approach, often realized through feedforward shift register structures with modulo-2 addition based on generator polynomials, yields codewords where the original message is fully obscured in the encoded form. For instance, a common rate-1/2 non-systematic code uses generator polynomials g(D)=(1+D2,1+D+D2)g(D) = (1 + D^2, 1 + D + D^2), producing outputs y1(D)=u(D)(1+D2)y_1(D) = u(D)(1 + D^2) and y2(D)=u(D)(1+D+D2)y_2(D) = u(D)(1 + D + D^2), where u(D)u(D) is the input polynomial. Such codes typically achieve a higher free distance dfreed_{\text{free}}, enhancing error-correcting performance, but data recovery necessitates complete decoding of the entire sequence since the input is not explicitly present. Systematic convolutional encoding, by contrast, incorporates the input bit stream unchanged as one or more of the output streams, supplemented by parity bits derived from linear combinations of the input and shift register contents. This structure simplifies partial data extraction, as the original message can be read directly from the systematic output without full error correction, which is advantageous for applications requiring low-latency access to information bits. However, including the input directly often results in a lower minimum distance compared to equivalent non-systematic codes, potentially reducing overall coding gain. For a rate-1/2 systematic code, the generators might take the form g(D)=(1,1+D+D21+D2)g(D) = \left(1, \frac{1 + D + D^2}{1 + D^2}\right), ensuring the first output matches the input while the second provides redundancy. In general, for a rate-k/nk/n code, the systematic generator matrix is structured as G(D)=[Ik×k ∣ R(D)]G(D) = [I_{k \times k} \ | \ R(D)], where Ik×kI_{k \times k} is the k×kk \times k identity matrix and R(D)R(D) is a k×(n−k)k \times (n-k) polynomial matrix generating the parity outputs. The choice between systematic and non-systematic forms involves key trade-offs in performance and complexity. Non-systematic codes offer superior minimum distance and coding gain—for example, a non-systematic rate-1/2 code with constraint length 3 can achieve dfree=5d_{\text{free}} = 5, yielding a coding gain γc=Rdfree=5/2\gamma_c = R d_{\text{free}} = 5/2 or approximately 4 dB—but require more involved decoding to retrieve data. Systematic codes, while potentially sacrificing some distance (e.g., reduced dfreed_{\text{free}} due to the unprotected input stream), enable delay-free encoding, non-catastrophic behavior, and minimal realizations, making them preferable for systems prioritizing encoding simplicity and partial decoding efficiency. Systematic forms are employed in various communication standards where these benefits outweigh the performance penalty, such as in certain wireless protocols that value straightforward implementation. Every convolutional code admits both systematic and non-systematic realizations, allowing transformation between them via algebraic operations on the generator matrix. To convert a non-systematic code to systematic, assuming the leading generator g1(D)g_1(D) has constant term 1, one premultiplies the generator tuple by 1/g1(D)1/g_1(D), yielding new generators where the first is 1 and others are adjusted accordingly; this preserves the code's overall properties while altering the encoding structure. For multi-input codes, reordering outputs or inverting submatrices of G(D)G(D) can achieve the systematic form [Ik ∣ R(D)][I_k \ | \ R(D)]. These conversions are typically performed during code design using shift register implementations, ensuring equivalence in the generated code space.

Code Architectures

Non-Recursive (Feedforward) Codes

Non-recursive, or feedforward, convolutional codes produce output symbols through linear combinations of the current input bit and past input bits stored in a shift register, achieved via connections known as taps, with no feedback path altering the input sequence. This structure relies on finite impulse response (FIR) filtering, where each output branch computes a modulo-2 sum of selected input bits based on the tap positions. The mathematical representation uses a time-invariant generator matrix G(D)G(D), a k×nk \times n matrix whose entries are polynomials in the formal delay variable DD, corresponding to the coefficients of the FIR filters in each branch. For an input sequence represented as a polynomial u(D)u(D), the output codeword polynomial is v(D)=u(D)G(D)v(D) = u(D) G(D), yielding a rate k/nk/n code where the degree of the polynomials determines the memory order. Feedforward codes simplify hardware realization, as their acyclic structure eliminates feedback loops, enabling straightforward implementation with shift registers and adders without the need for recursive state updates. Additionally, they mitigate catastrophic error propagation—where finite input errors produce infinite output errors—by choosing non-catastrophic generator polynomials; for rate 1/n1/n codes, this requires the greatest common divisor of all generator polynomials to be 1. A representative example is the rate 1/21/2, constraint length 3 feedforward code with generator polynomials g1(D)=1+D+D2g_1(D) = 1 + D + D^2 (octal 7) and g2(D)=1+D2g_2(D) = 1 + D^2 (octal 5), which is non-catastrophic since gcd⁡(1+D+D2,1+D2)=1\gcd(1 + D + D^2, 1 + D^2) = 1. This code, widely adopted in early communication standards, demonstrates the tap-based structure with two output branches and a 2-bit memory.

Recursive (Feedback) Codes

Recursive (feedback) codes, also known as recursive convolutional codes, incorporate a feedback mechanism in their encoder structure, where the input path depends on previous states through a recursive loop. This creates a dependence on prior inputs, typically implemented using a shift register with feedback connections that modify the input to the register based on a linear combination of past states modulo 2. Unlike feedforward codes, this recursion introduces a dynamic memory effect that propagates information indefinitely. The generator functions for recursive codes are expressed in rational form, with the feedback polynomial h(D)h(D) appearing in the denominator of the transfer function. For instance, a simple rate-1/2 recursive code can have a transfer function such as 11+D2\frac{1}{1 + D^2}, where the denominator represents the feedback path. In systematic recursive form, the output includes the unmodified input alongside the recursive parity bits, enhancing decodability. These codes exhibit an infinite impulse response due to the feedback loop, which contrasts with the finite response of non-recursive structures and can lead to longer error events. They offer potential for achieving higher free distance compared to equivalent non-systematic codes, improving error correction capability, but poorly designed feedback polynomials risk generating catastrophic codes, where finite input errors propagate to infinite decoding errors. Recursive systematic convolutional codes play a pivotal role as constituent components in turbo codes, where their recursive nature facilitates effective iterative decoding by producing high-weight codewords from low-weight inputs. A common example uses the feedback polynomial g(D)=1+D+D3g(D) = 1 + D + D^3, corresponding to octal representation 13, paired with a feedforward polynomial for the parity output.

Structural Properties

Constraint Length and Memory

In convolutional coding, the constraint length KK is a fundamental parameter that quantifies the memory inherent in the encoder structure. It is defined as K=m+1K = m + 1, where mm represents the maximum memory order or the number of memory elements (such as shift register stages) in the encoder. This means that each output symbol depends on the current input bit and up to mm previous input bits, spanning a total of KK consecutive input bits. The constraint length thus measures the "window" of input history that influences the encoding process, directly tying into the shift register implementation where past bits are stored to compute linear combinations via generator polynomials. For a general rate k/nk/n convolutional code, the constraint length KK is typically the same for all inputs and defined as K=m+1K = m + 1, where mm is the memory order per input stream, ensuring that the encoder's memory is captured consistently across branches. For binary rate 1/n convolutional codes (typically over GF(2)), the number of encoder states equals 2K−12^{K-1}, as each state is defined by the content of the K−1K-1 memory elements holding the previous input bits. The choice of constraint length embodies a key trade-off in convolutional code design: larger KK enhances error-correcting performance by increasing redundancy and allowing detection of longer error patterns, but it exponentially raises decoding complexity due to the growing number of states. For instance, a rate 1/21/2 code with K=7K=7 (thus m=6m=6) yields 64 states, a configuration that provides robust performance in practical systems like satellite communications while remaining feasible for Viterbi decoding, with each trellis branch reflecting transitions over the KK-bit input span. This balance has made moderate constraint lengths like K=5K=5 to K=9K=9 prevalent in standards, prioritizing achievable computational demands over marginal gains from very large KK.

Impulse Response and Transfer Function

The impulse response of a convolutional code characterizes the output sequence produced by the encoder in response to a unit impulse input, typically a single '1' bit followed by an infinite sequence of '0' bits. For a rate-1/n binary convolutional encoder, the impulse response is an n-tuple of sequences, each corresponding to one output branch, and its length is finite for non-recursive (feedforward) encoders, determined by the memory order mm, but infinite for recursive encoders due to feedback loops that prevent the state from returning to zero in finite time. The transfer function provides a frequency-domain (or z-transform) representation of the encoder's behavior, expressed as T(D)=N(D)D(D)T(D) = \frac{N(D)}{D(D)}, where N(D)N(D) is the numerator polynomial and D(D)D(D) is the denominator polynomial, both with coefficients in the finite field (e.g., F2\mathbb{F}_2). For feedforward encoders, the transfer function simplifies to T(D)=g(D)T(D) = g(D), a polynomial generator with D(D)=1D(D) = 1, reflecting the finite impulse response. In recursive encoders, feedback introduces a non-trivial denominator D(D)D(D), making T(D)T(D) a rational function that captures the infinite impulse response. These representations enable analysis of code properties, such as computing codeweight enumerators, which count the number of codewords of each weight to evaluate error-correcting performance. The transfer function T(D)T(D) generates output sequences as y(D)=u(D)⋅T(D)y(D) = u(D) \cdot T(D), where u(D)u(D) is the input polynomial, allowing enumeration of low-weight paths in the code trellis. A representative example is the rate-1/2 convolutional code with generator polynomials in octal notation (5,7), corresponding to g(0)(D)=1+D2g^{(0)}(D) = 1 + D^2 and g(1)(D)=1+D+D2g^{(1)}(D) = 1 + D + D^2, with memory order m=2m = 2. The impulse response yields output pairs: (1,1) at time 0, (0,1) at time 1, and (1,1) at time 2, followed by zeros, confirming the finite length tied to the memory. The transfer function is G(D)=[1+D2,1+D+D2]G(D) = [1 + D^2, 1 + D + D^2], used to derive weight enumerators for this feedforward code.

Graphical Representations

Trellis Diagrams

Trellis diagrams provide a graphical representation of the state transitions in a convolutional encoder over time, illustrating the possible sequences of states and outputs for a given code. In this structure, nodes represent the possible memory states of the encoder, with the number of states equal to 2m2^m, where mm is the memory order. The horizontal axis denotes time steps or input symbols, while branches connect states at consecutive time instants, labeled with the input bit and the corresponding output symbols generated during the transition. This construction captures the convolutional nature of the code by repeating a basic section, known as a trellis section, for each input symbol, forming an infinite or finite (for terminated codes) lattice-like diagram. Valid codewords correspond to paths through the trellis starting from the all-zero initial state and, for terminated codes, ending at the all-zero state after a finite length. Each path traces a unique sequence of branches, where merging paths between states highlight the code's redundancy, as multiple input sequences may converge to the same state, enforcing error-detecting properties. The divergence and subsequent merging of paths from a common state represent potential error events, visualizing how the code separates distinct messages over time. A representative example is the trellis for a rate-1/2 convolutional code with memory m=2m=2, yielding 4 states labeled as 00, 01, 10, and 11 (in binary, representing shift register contents). At each time step, an input bit of 0 or 1 causes transitions: for instance, from state 00, input 0 leads to state 00 with output 00, while input 1 leads to state 10 with output 11 (assuming standard generator polynomials). Branches from other states follow similarly, with the diagram showing parallel branches for each input possibility, forming a symmetric pattern that repeats across time. This 4-state trellis demonstrates how inputs drive state evolution, with outputs appended along the path to form the codeword. Trellis diagrams serve as the foundational structure for efficient decoding algorithms, enabling systematic exploration of all possible code paths to identify the most likely transmitted sequence. In particular, they facilitate the by allowing dynamic programming over the states, reducing computational complexity from exponential to linear in the number of branches per state. For codes with higher initial constraint lengths K>1K > 1, the trellis exhibits butterfly-like structures in early sections, reflecting the initial state uncertainty before settling into the periodic pattern.

State Diagrams

State diagrams offer a compact graphical representation of convolutional encoders as finite-state machines, capturing the evolution of the encoder's states without the time dimension inherent in trellis diagrams. Each node corresponds to a possible state of the shift registers, typically 2^{m} nodes for a code with order m, where the state is labeled by the binary content of the registers (e.g., "00", "01"). Directed edges connect states based on the next input bit, with labels indicating the input symbol and the resulting output symbols computed via the generator polynomials; for a rate-1/n , each edge is annotated as input/output , such as 0/00 or 1/11. This construction directly follows from the shift-register implementation, where advancing the state involves shifting in the new input bit and generating outputs as linear combinations modulo 2. For analytical purposes, particularly in deriving code performance metrics, a modified is employed. In this version, the all-zero state is split into a source node (initial state) and a node (final state), with no self-loop on the source; all other transitions form loops that may return to the . Edges are relabeled with variables tracking key properties: D raised to the of the output branch, N (or I) to the power of the number of input 1's on that branch, and optionally J (or L) for the branch length in symbols. This split-loop structure isolates paths from the source to the , representing divergent events that start and end in the zero state, while excluding the all-zero path. The diagram's reveals cycles corresponding to loops, with self-loops at non-zero states for zero-input transitions and cross-connections driven by input 1's. A representative example is the rate-1/2 convolutional code with constraint length K=3 (m=2), using generator polynomials g_1(D) = 1 + D + D^2 ( 7) and g_2(D) = 1 + D^2 ( 5). The four states are 00, 01, 10, and 11. From state 00, input 0 yields output 00 and stays at 00 (self-loop); input 1 yields 11 and goes to 10. From 01, input 0 goes to 00 with 11; input 1 to 10 with 00. From 10, input 0 to 01 with 10; input 1 to 11 with 01. From 11, input 0 to 01 with 01; input 1 to 11 with 10 (self-loop). In the modified version, the source connects only to non-zero states via input-1 branches, with loops like the self-loop at 11 labeled N D^1 J (for input 1, output 10) and cross-links such as from 10 to 11 labeled N D^1 J (input 1, output 01). This illustrates the split from source, loops among {01,10,11}, and returns to . These diagrams are instrumental in computing generating functions that enumerate error events. By applying or solving systems of linear equations from the branch gains (e.g., the T(D,N) = \sum N^{w_i} D^{w_o} over paths from source to sink, where w_i and w_o are input and output weights), the diagram yields the input-output weight enumerating function, which bounds bit and event error probabilities and identifies the free distance as the minimum exponent of D. This approach, foundational to performance analysis, relies on the diagram's acyclic paths in the modified form to sum contributions from all possible error cycles.

Performance Metrics

Free Distance

The free distance d\freed_{\free} of a convolutional code is defined as the minimum Hamming weight among all nonzero code sequences produced by the encoder. Due to the linearity of convolutional codes, this is equivalent to the minimum distance between any two distinct codewords. This parameter serves as a primary indicator of the code's error-correcting capability, as larger values of d\freed_{\free} enable the detection and correction of more errors before decoding failure occurs. The free distance can be computed using the of the code or its , which enumerates the weights of paths that start and end at the zero state while diverging from the all-zero sequence. For instance, the widely used rate-1/2 convolutional code with constraint length 7 and octal generators (171, 133), adopted as a standard for deep-space communications, has a free distance of 10. Algorithms based on modified Viterbi searches or generating functions facilitate this calculation, though they scale poorly with code complexity. In terms of performance, the free distance bounds the number of correctable errors at approximately t≈d\free/2t \approx d_{\free}/2, following the general sphere-packing principle for linear codes. Asymptotically, at high signal-to-noise ratios, the coding gain achieved by the code is given by 10log⁡10(Rd\free)10 \log_{10} (R d_{\free}) dB, where RR is the code rate; for the (171, 133) code, this yields about 7 dB. The free distance typically increases with the constraint length KK, enhancing error correction, but larger KK exponentially raises the computational demands for both encoding and distance evaluation due to the growing state space.

Error Events and Distribution

In convolutional codes, an error event refers to a finite-length path in the trellis that diverges from the all-zero reference path (corresponding to the transmitted codeword) and subsequently remerges with it. The length of such an event is measured by the number of branches from the divergence point to the remerge point, while the weight is the Hamming weight of the output symbols along that path, representing the number of differing bits relative to the all-zero sequence. These events model the typical decoding errors in maximum-likelihood decoding, where the decoder selects an incorrect path segment before correcting back to the true path. The statistical distribution of error events is captured by the weight enumerator A(D,I)=∑d,lad,lDdIlA(D, I) = \sum_{d, l} a_{d,l} D^d I^l, where ad,la_{d,l} denotes the number of error events with output weight dd and input weight ll (the number of 1s in the input sequence causing the event). This enumerator enumerates all possible low-probability paths starting and ending at the zero state in the trellis, excluding the all-zero path itself. It is derived from the code's T(D,I)T(D, I), a obtained by modifying the : branches are labeled with terms DwoIwiD^{w_o} I^{w_i}, where wow_o and wiw_i are the output and input weights of the branch, respectively; the transfer function is then computed as the rational expression T(D,I)=N(D,I)D(D,I)T(D, I) = \frac{N(D, I)}{D(D, I)}, with N(D,I)N(D, I) and D(D,I)D(D, I) being polynomials from solving the for state variables (or equivalently, via the inversion for the zero-state to zero-state paths). The coefficients of T(D,I)T(D, I) directly yield the ad,la_{d,l}, providing the spectrum of event weights and lengths essential for performance prediction. This distribution enables upper bounds on error performance, such as the union bound on the bit error rate Pb<1k∑d=d\free∞adQ(2dREbN0)P_b < \frac{1}{k} \sum_{d = d_{\free}}^\infty a_d Q\left( \sqrt{2 d R \frac{E_b}{N_0}} \right)
Add your contribution
Related Hubs
User Avatar
No comments yet.