This article mainly introduces the relevant applications of convolutional coding, and focuses on the application cases of convolutional coding in communication.
Convolutional codes
If we describe convolutional codes using (n, k, m), where k is the number of bits input to the convolutional encoder each time, n is the n-tuple codeword output by each k-tuple codeword, and m is the encoding storage degree, which is the number of levels of k-tuples in the convolutional encoder. m+1=K is called the encoding constraint degree, and m is called the constraint length. Convolutional codes encode k-tuple input codewords into n-tuple output codewords. However, k and n are usually very small, making them particularly suitable for serial transmission with low latency. Unlike block codes, the n-tuples generated by convolutional codes are related not only to the current input k-tuple but also to the previous m-1 input k-tuples. The number of interconnected codewords during the encoding process is n*m. The error correction performance of convolutional codes increases with increasing m, while the error rate decreases exponentially with increasing N. With the same encoder complexity, convolutional codes outperform block codes.
The error correction capability of convolutional codes depends not only on the constraint length but also on the decoding method used. In summary, due to the small size of n and k and the utilization of the correlation between groups, under the same code rate and device complexity, both theoretically and practically it has been proven that the performance of convolutional codes is at least no worse than that of block codes.
Applications of convolutional coding in communication
Basic Concepts
To understand convolution, one must first understand the concepts of impulse signals and impulse responses. In a linear time-invariant system, any signal can be decomposed into a combination of impulse signals. An impulse signal, however, is a signal that doesn't actually exist; it's defined as a signal that has a value at a specific time point and is zero at all other time points. A unit impulse signal, also called a delta function, is a signal with its amplitude normalized to 1, where the value is 1 at sampling point 0 and 0 at all other points. An impulse signal can be understood as the result of quantization and shifting a unit impulse signal. In essence, impulse decomposition provides a method to analyze only one sampling point at a time. When the unit impulse is the input, the system output signal is the impulse response.
In linear systems, convolution is used to describe the relationship between the input signal, impulse response, and output signal.
The diagram below shows how convolution is used to implement low-pass and high-pass filtering.
The following section details the mathematical description of convolution, which can be viewed from the perspectives of input and output signals.
Viewing convolution from the perspective of input signal
First, from the perspective of the input signal, we need to examine the contribution of each input sampling point to the output signal. As shown in the diagram below, a signal with 9 input points passes through a system with an impulse response at 4 sampling points; its block diagram is as follows.
From the perspective of each input signal sampling point, the output is the result of multiplying the unit impulse response by a coefficient and shifting it. Therefore, the figure below shows the result of all 9 sampling points passing through the system.
Therefore, we can obtain the output after the system passes through 9 sampling points. Another property of convolution is that the two inputs can be interchanged, i.e., a*b = b*a. The analysis of the impulse response system for a 4-input signal passing through 9 sampling points, after swapping the two inputs in the above example, is as follows:
The procedure for viewing convolution from the perspective of the input signal is as follows:
The core of this is line 240. For example, for the 40th sample point of the input signal, the inner loop performs three things at each point using the impulse response: First, the impulse response is multiplied by an input sample value for quantization. Second, the quantization impulse is shifted 40 sample points to the right. Finally, the output value is summed with the result from each input sample point.
Viewing convolution from the perspective of output signal
From the perspective of the input signal, each sample point of the convolution input affects multiple samples of the output signal. From the second perspective, we look at each sample point of the output signal individually, considering which input signal samples generate each sample point. Suppose we want to find the convolution output of a given set of input signals and impulse responses; the most intuitive method is to calculate the output of each sample point of the output signal. This requires knowing how to calculate the result of each sample point of the output signal. Suppose we want to find out which inputs affect the result of y(6). By looking at the result diagram of all 9 input sample points passing through the system, we can see that x(3), x(4), x(5), and x(6) affect y(6) through the output components of the impulse response.
y(6)=x(3)h(3)+x(4)h(2)+x(5)h(1)+x(6)h(0)
The diagram below illustrates the output algorithm as a convolutional converter, and the flowchart shows how convolution is performed.
A convolutional converter can be viewed as a black box that can move left and right. Four input signal sampling points enter the input terminal, and these values are multiplied by the value represented by the impulse response and the results are added together. For example, y(6) is calculated from x(3) , x(4) , x(5) , and x(6). To calculate y(7), the convolutional converter moves one position to the right, and another four inputs x(4)-x(7) enter the convolutional converter. This process is repeated for all points where the output signal needs to be calculated.
In the convolutional diagram above, the impulse response is shifted left and right; this shifting is simply for mathematical convenience. The impulse response describes how each input signal point affects the output signal. The result for each point of the output signal is influenced by multiplying the input signal by a flipped impulse response.
The following figure shows the boundary treatment.
Calculating y(0) requires x(-3) , x(-2) , x(-1), and x(0), but x(-3) , x(-2) , and x(-1) do not exist. This situation is handled by adding 0 to the boundary.
In DSP terminology, this situation, where the output signal is based on incomplete information, is called an impulse response that is not fully immersed in the input signal. If the impulse response length is M points, then the first to the (M-1)th sample points in the output signal are based on incomplete input information. This is similar to electronic circuits, which require a certain amount of time to stabilize the power supply. The difference is that this transient is easily ignored in electronics, but it is very significant in DSPs.
The diagram below illustrates the problems caused by this effect, where the input signal is a sine wave with a DC component added , and the goal is to remove the DC portion of the signal.
As shown in the figure, problems occur with 30 signals before and after the input. This "end-effect" problem is very common in DSPs. Therefore, the general rule is to discard some of the first and last sampling points when processing signals.
Next is the mathematical formula for convolution:
The formula allows for the calculation of output signal samples one by one. To calculate a certain output sample, the exponent j is traversed from 0 to M-1, and each impulse response sample h[j] is multiplied by the appropriate input sample signal x[xj] and then added together.
The same procedure for performing convolution is shown below:
Unlike input-side programs that iterate through input sampling points, output-side programs iterate through output signal sampling points. It's worth noting that there are several ways to define the output signal for a signal with only 80 input sampling points. For example, you can extend the input sampling points by adding 0s to the boundaries, or you can only process signals from 30 to 80.
Sum of weighted inputs
Both of the above analyses can yield the results of convolution. Looking back at the convolutional machine above, if we consider the impulse response as a set of weighted coefficients, then each output signal sample point equals the sum of the weighted inputs. Which input signals influence each output sample point depends on the selection of the weighted coefficients.
