MindMap Gallery error control coding
Several coding systems are introduced, including the basic principles of error correction coding, the performance of error correction coding, simple practical coding, linear block codes, etc.
Edited at 2024-02-18 10:52:10Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
error control coding
Overview
error control coding
error control method
3 types of automatic repeat request (ARQ) systems
Stop waiting for ARQ system
Pull back ARQ system
Select retransmission ARQ system
Main advantages of ARQ
The code rate is higher. ∵The bit error rate can be reduced to a very low level with fewer supervision symbols; the computational complexity of error detection is low; the coding method used for error detection has basically nothing to do with the statistical characteristics of additive interference, and can be adapted to channels with different characteristics .
Main disadvantages of ARQ
A two-way channel is required for retransmission, and is not suitable for one-way channels and point-to-multipoint communication systems. Resending reduces the transmission efficiency of the ARQ system. When channel interference is severe, de facto communication interruption will occur due to repeated retransmissions. Not suitable for situations requiring real-time communication, such as telephone communication.
Principle block diagram of ARQ system
Basic principles of error correction coding
Block code and system code
Code weight and code distance
The relationship between the minimum code distance d0 and error detection and correction capabilities
Error correction coding performance
The contradiction between system bandwidth and signal-to-noise ratio
The relationship between transmission rate RB and signal-to-noise ratio Eb/n0
Simple practical coding
parity supervision code
Two-dimensional even supervision code
constant ratio code
positive and negative code
linear block code
basic concept
The construction principle of Hamming code
Characteristics of Hamming code:
General principles of linear block codes
H---Supervision matrix
Properties of H matrix
G---generating matrix
Properties of G matrix
The relationship between G and H
Correction and error patterns
Properties of linear block codes
①Closedness
②Minimum distance
network coding modulation
Basic concepts of TCM
QPSK is a 4-phase phase shift keying system that transmits 2 bits of information per symbol. If the signal phase is misjudged to an adjacent phase due to interference during the receiving end decision, a code error will occur. Now the system is changed to 8PSK, and each symbol of it can transmit 3 bits of information. However, each symbol is still allowed to transmit 2 bits of information, and the third bit is used for error correction code. For example, a convolutional code with a code rate of 2/3 is used. At this time, the demodulation and decoding at the receiving end are completed as one step. Unlike the traditional method, the baseband signal is first demodulated and then decoded for error correction.
Generation of TCM signal
Divide the signal constellation diagram into several subsets so that the distance between signal points in the subsets is larger than the original one. Each time it is divided, the distance between signal points in the new subset increases.
Demodulation of TCM signals
Demodulation algorithm of TCM signal
The Viterbi algorithm is usually used, but the current grid diagram represents the state of the waveform rather than the code group.
The task of the decoder is to calculate the distance between the received signal sequence path and various possible coding grid paths
If all transmitted signal sequences are equally likely, then the possible path with the smallest distance from the received sequence (also called the maximum likelihood path) is determined to be the transmitted sequence.
Because convolutional codes are linear codes and have closed properties, the path distance to be examined has nothing to do with the test sequence used. Therefore, without loss of generality, you can choose an all-“0” sequence as the test sequence.
Free Euclidean distance Fed:
The free Euclidean distance refers to the minimum distance between elements in the set of allowed waveform sequences. It determines the probability of wrong decisions. The larger the free Euclidean distance, the smaller the probability of wrong decision.
low density parity check code
Introduction to LDPC code
LDPC code is a linear block code, which belongs to the same category of composite codes as Turbo code. The performance of the two is similar, and the decoding delay of both is quite long, so they are more suitable for some communications that do not require very high real-time performance. . However, the decoding of LDPC codes is simpler and easier to implement than Turbo codes.
LDPC code classification
Regular LDPC code: H matrix has the same number of "1"s in each column Irregular LDPC code: The number of "1's in each column of the H matrix is not necessarily the same. The irregular LDPC code is developed on the basis of the regular LDPC code. It improves the decoding performance and makes the bit error rate performance better than the Turbo code. .
Construction of LDPC code:
The LDPC code is the same as the ordinary parity supervised code and can be determined by the supervision matrix H with n columns and m rows; n is the code length and m is the number of syndromes. However, its H matrix is different from that of ordinary parity supervision codes: it is a sparse matrix, that is, the number of "1"s in the matrix is very small, and the density is very low; suppose that the H matrix has j "1"s in each column and j "1"s in each row. With k "1"s, there should be j<<m, k<<n, and j3. The elements of any two rows of its H matrix cannot be "1" at the same position, that is, there is no rectangle with four corners composed of "1" in the H matrix. LDPC codes are usually represented by the above three parameters (n, j, k). During coding, after designing the H matrix, the generator matrix G can be derived from the H matrix. In this way, for a given information bit, it is not difficult to calculate the code group.
Decoding of LDPC code:
The decoding method of LDPC codes is also different from the decoding method of general parity supervised codes. The basic decoding algorithm is called the belief propagation algorithm, often referred to as the BP algorithm. This algorithm essentially seeks the maximum posterior probability, similar to the general maximum likelihood criterion decoding algorithm, but it requires multiple iterative operations to gradually approach the optimal decoding value. The specific encoding and decoding algorithm of LDPC code is very complicated and will not be discussed in depth here.
Turbo code
Basic principles of Turbo code
Since the complexity of block codes and convolutional codes increases exponentially with the increase of code group length or constraint degree, in order to improve the error correction capability, do not simply increase the length of the code, but combine two or more simple Codes are combined into composite codes.
The encoder of Turbo code adds an interleaver between two parallel or series component code encoders, so that it has a large code group length and can obtain close to ideal performance under low signal-to-noise ratio conditions.
The decoder of the Turbo code has two component code decoders. The decoding is iteratively decoded between the two component decoders. Therefore, the entire decoding process works like a turbine, so it is also vividly called Turbo. code
Turbo code encoder
The main difference between RSCC encoders and convolutional code encoders: There is a feedback path from the output of the shift register to the input of the information bits. The original convolutional code encoder is like a FIR digital filter. After adding a feedback path, it becomes an IIR filter, or recursive filter.
convolutional code
Symbol of convolutional code: (n,k,N)
N---coding constraint degree, indicating the number of code segments that constrain each other during the encoding process;
nN---encoding constraint length, indicating the number of code elements that are constrained to each other during the encoding process.
N or nN also reflects the complexity of the convolutional code encoder.
The code rate of convolutional code:
R=k/n
Basic principles of convolutional codes
Encoder principle block diagram
The expression method of convolutional code
Algebraic representation of convolutional codes
Supervision matrix H
Still taking the previous (3,1,3) convolutional code as an example for analysis. Assuming that the shift registers at all levels are initially in the "0" state, the relationship between the supervision bits di, ei and the information bit bi can be written as:
The general form of truncated supervision matrix H1 is:
Basic supervision matrix h
h is one of the most important matrices of convolutional codes. As long as h is given, H1 can be constructed.
Generating matrix G
Truncated generating matrix G1
Basic generating matrix g
Decoding of convolutional codes
Classification
algebraic decoding
Decoding is performed using the algebraic structure of the encoding itself, without considering the statistical characteristics of the channel.
probabilistic decoding
Calculation based on the statistical characteristics of the channel and the characteristics of the convolutional code
Large number logic decoding
working principle
First, the received information bits are temporarily stored in the shift register, and syndromes are calculated from the information bits and supervisory bits of the received symbols. Then, the calculated syndrome is temporarily stored and used to detect the location of the error code. At the output end of the information bit shift register, there is a modulo 2 addition circuit; when an error in the output information bit is detected, "1" is added to the output information bit to correct it.
Decoder block diagram
Geometric representation of convolutional codes
1) Code tree diagram
2) State diagram
3) Grid diagram
Viterbi decoding algorithm
Basic principle: Compare the received signal sequence with all possible transmitted signal sequences, and select the sequence with the smallest Hamming distance as the current transmitted signal sequence.
cyclic code
Cyclic code principle
Cyclicity:
It means that after any code group is cyclically shifted (moving the rightmost symbol to the left, or vice versa), it is still an allowed code group in the code.
code polynomial
Modulo operation of code polynomials
Generating matrix G of cyclic code
Encoding and decoding methods of cyclic codes
Cyclic code encoding
coding circuit
It can be implemented using a division circuit composed of (n – k) stage shift registers.
Decoding of cyclic codes
truncated cyclic code
truncation purpose
When designing an error correction coding scheme, if a suitable code length n and information bit k cannot be found, the code length of the cyclic code can be truncated to obtain a code that meets the requirements.
truncation method
Assume that a (n, k) cyclic code is given, which has a total of 2^k code groups. Now its first i (0 < i < k) information bits are all "0", so it becomes only 2^ (k-i) Seed code group. Then delete the information bits of all "0" in the i bits, and finally obtain a linear code of (n –i, k –i) - a truncated cyclic code.
Truncated cyclic code performance
The cyclic code has at least the same error correction capability before and after truncation, and the encoding and decoding method is still the same as before truncation.
BCH code
definition
A widely used cyclic code capable of correcting multiple error codes, named after three inventors.
The importance of BCH code
——The problem of the relationship between the generator polynomial and the error correction capability is solved, and the generator polynomial of the code can be found under the given error correction capability requirements. ——With the generator polynomial, the basic problem of encoding is solved.
Classification of BCH codes
Primitive BCH code: Its generating polynomial g(x) contains a primitive polynomial with the highest degree m, and the code length is n= 2^m-1, (m≥3, a positive integer).
Non-primitive BCH code: its generator polynomial does not contain this primitive polynomial, and the code length n is a factor of (2^m-1), that is, the code length n must be divided by 2^m-1.
BCH code performance
The relationship between the code length n, supervision bits, and the number of error corrections t: For a positive integer m (m 3) and a positive integer t < m / 2, there must be a code length n = 2^m – 1 with supervision bits is n – k mt, which can correct all BCH codes with no more than t random errors. If the code length n = (2^m - 1) / i (i > 1, and all divisions can be made (2^m -1)), it is a non-original BCH code.
Hamming codes are codes that can correct a single random error. It can be proved that the Hamming code with cyclic properties is the original BCH code that can correct a single random error.
Design of BCH code
In engineering design, it is generally not necessary to use calculation methods to find the generating polynomial g(x). Because predecessors have already listed the found g(x) in a table, we can use the table lookup method to find the required generator polynomial.
RS code