① source code. Transform the signal output by information sources, including discretization of continuous signals, that is, convert analog signals into digital signals through sampling and quantization, and compress the data to improve the effectiveness of digital signal transmission.
② Channel coding. Re-transform the signal output by the source encoder, including coding to distinguish channels, adapt to channel conditions and improve communication reliability.
③ Security coding. Re-transform the signal output by the channel encoder, that is, coding makes the information difficult to be stolen in the transmission process. Coding theory is widely used in digital telemetry and telecontrol system, electrical communication, digital communication, image communication, satellite communication, deep space communication, computing technology, data processing, image processing, automatic control, artificial intelligence and pattern recognition. Forward error correction (FEC) is a technique to control transmission errors in one-way communication systems. It restores errors by sending extra information with data to reduce the bit error rate (BER). FEC is divided into in-band FEC and out-of-band FEC. The processing of FEC usually takes place in the early stage, and the processed digital signal is received for the first time. In other words, the error correction circuit is often an inseparable part in the process of analog-to-digital conversion, which also involves digital modulation and demodulation, or line coding and decoding.
FEC adopts a predetermined algorithm by adding redundant information for transmission. In 1949, Hamming proposed a hamming code that can correct a single random error. 1960, Hoopueghem, Bose and Chaudhum invented BCH code, and Reed and Solomon proposed ReedSolomon(RS) code, which has strong error correction ability and was later called Reed-Solomon error correction code (later additional forward error correction). ITU-T G.975/G.709 stipulates that "out-of-band FEC" means adding an FEC layer under SDH layer to deal with FEC problems. Out-of-band FEC coding has great redundancy and strong error correction ability. Unlike ARQ, FEC does not need to inform the sender of retransmission errors. Once the system loses the original data packet, FEC mechanism can supplement it with redundant data packet. For example, a packet is "10", which is divided into two packets, namely "1" and "0", and there is a redundant packet "0". After receiving any two data packets, the original packet can be assembled. However, these redundant data packets will also generate additional burden. 1843, the famous American painter S.F.B Morse carefully designed Morse code, which was widely used in telegraph communication. Morse code uses three different symbols: dot, dash and interval, which can be regarded as sequential ternary code. According to the coding theory, it can be proved that the difference between Morse code and the theoretically achievable limit is only 15%. But it was not until 1930s and 1940s that coding theory began to take shape. 1928, H. Nyquist, an American telecom engineer, put forward the famous sampling theorem, which laid the foundation for the discretization of continuous signals. 1948, American applied mathematician C. E. Shannon put forward the concept of information entropy in his article Mathematical Theory in Communication, which laid a theoretical foundation for source coding. 1949, Shannon put forward the concept of channel capacity and channel coding theorem in the article Communication with Noise, which laid a theoretical foundation for channel coding. The coding theorem of noise channel (also known as Shannon's first theorem) points out that the average length of codewords can only be greater than or equal to the entropy of the source. The coding theorem of noisy channel (also known as Shannon's second theorem) is the existence theorem of coding. (See Shannon's Three Theorems) It points out that as long as the information transmission rate is less than the channel capacity, there is a coding, so that the error probability of information transmission can be arbitrarily small. With the development of computing technology and digital communication, error-correcting coding and cryptography have developed rapidly.
As far as source code is concerned
Shannon proved in 195 1 that when the source outputs redundant messages, the output of the source can be changed by coding, so that the information transmission rate is close to the channel capacity. In 1948, Shannon proposed Shannon coding which can match the source and channel. 1949, R.M. Feno of Massachusetts Institute of Technology proposed Feno coding. 195 1 year, American telecom engineer D.A. Huffman proposed a more effective Huffman coding. Since then, fax coding, image coding and voice coding have appeared, and data compression has been deeply studied, which has solved many practical problems in digital communication.
In error correction coding
In 1948, Shannon proposed a bit error correcting code (codeword length =7, information symbol number =4). Gray code with three-bit error correction in 1949 (codeword length =23, number of information symbols = 12). 1950, Richard Wesley Hamming, an American mathematician, published his paper Error Detection Code and Error Correction Code, and put forward the famous Hamming Code, which had an important influence on error correction coding. Convolutional code appears in 1955. Convolutional codes are still widely used. 1957 introduces cyclic codes. Cyclic codes are simple in structure, easy to design with algebraic theory and easy to realize. Hagberger code and Fell code appeared in 1959, which can correct sudden errors. 1959, R.C. Bos and D.K. Ray Chaudhry of the United States and A. Okungun of France published a famous cyclic code almost simultaneously and independently, which was later called BCH code. 1965 proposes sequential decoding, which has been used in space communication. 1967 A.J. Viterbi proposed maximum likelihood convolutional decoding, which is called Viterbi decoding. Vector coding appears in 1978. Vector coding is an effective coding technique. 1980 Reed-Solomon code (RS code for short) was realized by number theory. It is actually a multiband BCH code. This error correction coding technique can reduce the number of components in the encoder integrated circuit by an order of magnitude. It has been widely used in satellite communication. The concatenated code composed of RS code and convolutional code can be used in deep space communication.
In cryptography,
1949, Shannon published Communication Theory of Security System, which is generally considered as the pioneering work of cryptography. 1976, Duffy and Herman first proposed the public key cryptosystem, which opened up a new direction for the study of cryptography. The application of VLSI and high-speed computer promotes the development of security coding theory, but it also poses a great threat to the security of secure communication. Since 1970s, the theory of computational complexity has been introduced into cryptography, and so-called P-class, NP-class and NP-complete problems have emerged. The complexity function of the algorithm increases exponentially, so the key space expands, which makes the analysis and search of passwords face severe challenges. Cryptography began to develop in depth.