13:38 FEC Part 1 | |
IntroductionEveryone knows that the transmission of information via communication channels, it can be distorted, that is, an error may occur in the transmitted message. Misrepresentation may occur for various reasons: because of problems in transmitting or receiving equipment, interference in the communication channel from external sources or because of his injury. In order to protect the information using various methods, however, the best known and most convenient is the use of error-correcting coding information, that is, coding, controlling and correcting errors. History of error-correcting codingHistory of the coding supervisory errors that began in 1948 with the publication of Claude Shannon's famous article "A Mathematical Theory of Communication." Shannon showed that with each channel is connected is measured in bits per second and is called the bandwidth number C. If required by the communication system data transfer rate R (measured in bits per second) is less than C, then, using codes that control errors, the channel can construct a communication system that the probability of error at the output is arbitrarily small. In fact, from Shannon's information theory should be the important conclusion that the building is too good channels is wasteful, economically advantageous to use encryption. Shannon, however, did not indicate how to find the appropriate codes, but only to prove their existence. In the fifties, much effort has been spent on attempts to construct an explicit class of codes that provide a promise of an arbitrarily small probability of error, but the results were meager. In the next decade, the decision of this fascinating problem has received less attention, but instead of codes, researchers have taken a long attack on two main fronts. The first area was purely algebraic nature and mostly considered block codes. The first block codes were introduced in 1950, when the Hamming described the class of block codes detecting single error (ie, the transmitted data packet corrected an error). Hamming codes were very weak compared to the Shannon promised a much more powerful codes. Despite substantial research, by the end of the fifties was not built a better class of codes. The main shift occurred when Bowes and Roy-Chowdhury and Hokvingem found a large class-Correcting Codes multiple error (that is, changed a few characters in the data packet), and Reed Solomon codes have found a class for non-binary channels. Although these codes are among the most important classes of codes, the general theory of block codes, error control, since its successful development. The second line of research on coding was of more probabilistic in nature. The studies were related attempts to understand the encoding and decoding with probabilistic point of view, these attempts have resulted in sequential decoding. In sequential decoding, we introduce a class Nonblock codes of infinite length, which can be described by a tree and decoded using the search algorithms on a tree. The most useful tree-codes are codes with a fine structure, known as convolutional codes. In the 70 years these two research areas were again intertwined. Theory of convolutional codes is engaged algebraists presented it in a new light. In the theory of block codes in that time managed to get closer to the codes promised by Shannon: proposed two different coding schemes that allow to build a family of codes, which can simultaneously have a very large block length and a very good performance. Both schemes, however, have practical limitations. Meanwhile, in the early 80's encoders and decoders have started to appear in the construction of digital communication systems and digital memory systems. Encoding with error correction, in essence, is a method of signal processing, designed to increase reliability of transmission over digital channels. Although various encoding schemes are very dissimilar and are based on various mathematical theories, they all have two common properties. One of them - the use of redundancy. Encoded digital messages will always contain additional, or redundant, and symbols. These symbols are used to emphasize the individuality of each message. They are always selected so as to make unlikely the loss of the message of his personality due to distortion when exposed to noise of a sufficiently large number of characters. The second property consists in averaging the noise. Averaging effect is achieved due to the fact that the excess characters depend on a number of information symbols. To date, developed a lot of different error-correcting codes, which differ from each other grounds, distance, redundancy, structure, functionality, energy efficiency, correlation properties, encoding and decoding algorithms, the shape of the frequency spectrum. Application error-correcting codingSince the development of Error Control Codes, initially stimulated by tasks of communication, terminology, coding theory stems from the theory of communication. Constructed codes, however, have many other applications. Codes are used to protect data in memory and computing devices on digital tapes and discs, as well as protection against malfunction or noise in digital logic circuits. Codes are also used for data compression and coding theory is closely connected with the theory of planning statistical experiments. Applications to problems of communication are very different. Binary data is typically transferred between the computing terminals, between aircraft and between satellites. Codes can be used to provide reliable communications even when the power of the received signal is close to the power of thermal noise. And because the electromagnetic spectrum, more and more filled with the signals created by man, the codes that control the errors become even more important tool as they allow the lines of communication to work reliably in the presence of interference. In military applications, such codes are often used for protection against deliberately organized enemy interference. In many communication systems there is a limit on transmitted power. For example, on the relay satellite capacity increase is very expensive. Codes, error control, are a great tool to reduce the required power, because they can be properly restored impaired received the message. Transmission in computer systems typically sensitive to even very small fraction of errors, since a single mistake can disrupt the calculation program. Coding, Error Control, becomes in these applications is very important. For some media memory usage of Error Control Codes, allows for more dense packing of bits. Another type of communication system is a system with many users, and time division, in which each of a given number of users, some pre-prescribed time windows (intervals), in which he is allowed to transfer. Long binary messages are divided into packets and one packet is transmitted in the allotted time window. Because of the timing errors or mistakes of equipment, some packets may be lost. Appropriate codes, error control, protect against such losses, since lost packets can be recovered from known packs. Communication is also important within a single system. In today's complex digital systems may have large flows of data between subsystems. Digital autopilot, digital process control systems, digital switching systems and digital systems for processing of radar signals - all of which contain large amounts of digital data that must be distributed between many interrelated subsystems. These data should be transferred to or specifically designed for this lines, or through more complex systems with tire data transmission and time division. In any case, the important role played by the methods of coding, Error Control, as they allow us to guarantee appropriate characteristics. PS:All the material was collected from various books and the Internet. If the topic seems interesting, I'll write the second part, which will be considered the simplest codes. UPD: A more appropriate category than the "Information Security" is not found. UPD 2: References and materials.
| |
|
| |
| Total comments: 0 | |