Discrete information transmission systems with feedback(OS) are called systems in which the repetition of a previously transmitted one occurs only after receiving the OS signal. Feedback systems are divided into systems with a decisive OS and an information OS.
Decisive feedback systems
In the receiver of the system, the correctly received combinations are accumulated in the accumulator, and if, after receiving the block, at least one of the combinations is not accepted, then a re-request signal is generated, which is the same for the entire block. The whole block is repeated again, and in the receiver of the system, the combinations that were not received during the first transmission are selected from the block. Repeated queries are made until all combinations of the block are accepted. After all combinations are received, a confirmation signal is sent. Having received it, the transmitter transmits the next block of combinations (systems with address re-interrogation - ROS-AP). These systems are in many respects similar to systems with accumulation, but unlike the latter, the receiver generates them and transmits a complex re-request signal, which indicates the conditional numbers (addresses) of the block combinations not received by the receiver. In accordance with this signal, the transmitter does not repeat the entire block, as in the accumulation system, but only not received combinations (systems with sequential transmission of code combinations - POC-PP).
There are various options for constructing ROS-PP systems, the main of which are:
Systems with changing the order of combinations (ROS-PP). In these systems, the receiver erases only the combinations according to which the decision device has made a decision to erase, and only for these combinations sends the re-request signals to the transmitter. The rest of the combinations are issued to the PI as they are received.
Systems with the restoration of the sequence of combinations (ROS-PP). These systems differ from ROS-PP systems only in that their receiver contains a device that restores the sequence of combinations.
Variable sealing systems (ROS-PP). Here, the transmitter alternately transmits combinations of the sequences, the number of the latter being chosen so that by the time the combinations are transmitted at the transmitter, the OS signal has already been received according to the previously transmitted combination of this sequence.
Systems with blocking of the receiver for the time of receiving combinations after detecting an error and repetition or transfer of a block from combinations (ROS-PP).
Blocked combinations control systems (ROS-PP). In these systems, after detecting an error in the codeword and transmitting the re-request signal, a check is made for the presence of detected errors h -1 combinations following the combination with the detected error.
Information feedback systems
The difference in the logic of operation of systems with POC and IOS is manifested in the transfer rate. In most cases, the transmission of service characters requires less energy and time than transmission over direct channel identifiers in the system with ROS. Therefore, the transmission rate of messages in the forward direction in a system with an ITS is higher. If the noise immunity of the reverse channel is higher than the noise immunity of the forward channel, then the reliability of message transmission in systems with ITS is also higher. In the case of complete noiseless information feedback, it is possible to ensure error-free transmission of messages over the forward channel, regardless of the level of interference in it. For this, it is necessary to additionally organize the correction of the service characters distorted in the direct channel. Such a result, in principle, is unattainable in systems with distributed type DFB. In the case of grouping errors, an essential role is played by the conditions in which the information and control parts of the code combinations are transmitted in both communication systems. When using IOS, there is often a single decorrelation of errors in the forward and reverse channels.
The length of the used code n and its redundancy s / t also play an important role when comparing message transmission with POC and IOC. If the redundancy is small (s / n<0,3), то даже при бесшумном обратном канале ИОС практически не обеспечивает по достоверности преимущества перед РОС. Однако скорость передачи у систем с ИОС по-прежнему выше. Следует указать еще одно преимущество систем с ИОС, обусловленное различием в скорости. Каждому заданному значению эквивалентной вероятности ошибки соответствует оптимальная длина кода, при отклонении от которой скорость передачи в системе с РОС уменьшается. В системах с ИОС при s/n>0,3 it is more profitable to send messages in short codes. With a predetermined reliability, the transmission rate becomes higher because of this. This is beneficial from a practical point of view, since encoding and decoding with short codes is easier. With an increase in code redundancy, the advantage of systems with ITS in transmission reliability increases even with forward and reverse channels of the same noise immunity, especially if the transmission of messages and receipts in a system with ITS is organized so that errors in them are uncorrected. The energy gain in the forward channel of the system with IOS turns out to be an order of magnitude higher than in the system with DFB. Thus, the ITS in all cases provides equal or higher noise immunity of message transmission over the forward channel, especially at large s and a noiseless return channel. The ITS is most efficiently used in such systems where the reverse channel, due to the nature of its load, can be used for efficient transmission of acknowledgment information without prejudice to other purposes.
However, the overall complexity of the implementation of systems with ITS is greater than that of systems with ROS. Therefore, POC systems have found wider application. Systems with ITS are used in cases where the reverse channel can be effectively used for transmitting receipts without prejudice to other purposes.
There are often cases when information can be transmitted not only from one correspondent to another, but also in the opposite direction. In such conditions, it becomes possible to use the reverse flow of information to significantly increase the fidelity of messages transmitted in the forward direction. It is possible that both channels (forward and backward) mainly directly transmit messages in two directions ("duplex communication") and only part of the bandwidth of each channel is used to transmit additional data intended to improve fidelity.
Possible different ways using a feedback system in a discrete channel. They are usually classified into two types: information feedback systems and control feedback systems. Systems with information feedback are those in which information is received from the receiving device to the transmitter about the form in which the message was received. Based on this information, the transmitting device can make certain changes in the message transmission process: for example, repeat erroneously received message segments, change the code used (by transmitting the corresponding conditional signal in advance and making sure that it is received), or even stop transmission in case of a bad state the channel before it is improved.
In systems with control feedback, the receiving device, based on the analysis of the received signal, itself makes a decision about the need to repeat, change the transmission method, temporarily interrupt communication, and sends an order to the transmitting device. Mixed methods of using feedback are also possible, when in some cases the decision is made at the receiving device, and in other cases at the transmitting device based on the information received via the reverse channel.
In theory, the simplest informational feedback method is the complete reverse check and repeat (FRE) method. In this case, the received signal is completely retransmitted to the transmitting device, where each received codeword is checked against the transmitted one. If they do not match, the transmitting device transmits a signal to erase the incorrectly received combination, and then repeats the desired combination. As a signal for erasing, a special code combination is used, which is not used when transmitting a message.
The functional diagram of such a system is shown in Fig. 5.L The transmitted message, encoded with a primitive code, is sent to the channel and simultaneously recorded in the storage device. The received codeword is not immediately decoded, but is stored in the receiving storage and is returned via the return channel to the transmitting end, where it is compared with the transmitted combination. If they match, then the next code combination is transmitted, otherwise - the erasure signal.
With this method, the final erroneous reception of the code combination is possible only when the errors in the received combination are compensated for by the errors occurring in the feedback channel. In other words, in order for some symbol in the transmitted codeword to be finally received erroneously, it is necessary and sufficient that, firstly, an error occurs in the forward channel and, secondly, an error occurs during retransmission that will change the incorrect relayed symbol to really transmitted. This allows you to immediately calculate the probability of an undetected, and, consequently, uncorrected error (per character):
р n.o = p 1 p 2 (5.33)
where p 1 is the error probability in the forward channel; p 2 - the probability of the opposite error in the feedback channel.
Therefore, if p 1 and p 2 are large, then the full relay system gives unsatisfactory results. Practically this method makes sense in cases where the feedback channel provides a very high fidelity (for example, when transmitting messages to the satellite from the Earth), and the forward channel has low fidelity (for example, when transmitting satellite messages to the Earth due to the fact that the transmitter power on the satellite is low ). A significant drawback of a system with full retransmission is the high load on the feedback channel. There are also more complex systems with information feedback, which use error-correcting codes.
The most common systems with control feedback (FOC) using redundant codes to detect errors (Fig. 5.2). Such systems are often referred to as over-demand or automatic error-request or decision feedback (POC) systems.
In most cases, these are duplex systems, that is, information is transmitted in them in both directions. In the encoder, the transmitted message is encoded with a code that makes it possible to detect errors occurring in the channel with a high probability. The received code block is decoded with error detection. If no errors are found, then the decoded segment of the message goes to the recipient. If errors are detected, the block is rejected and a special "re-request signal" is transmitted over the return channel. In most systems, this signal is a special code combination, during the transmission of which the flow of information going through the reverse channel is interrupted. Reception of the re-request signal causes a repetition of the rejected block, which for this purpose is stored in the drive-repeater until the next code combination, which does not contain the re-request, is received via the reverse channel.
The system with control feedback is very effective in channels with variable probability of error p (for example, in fading channels). When the value of p becomes close to 1/2, i.e., the channel capacity drops almost to zero, the system is in a constant over-demand mode, but at good code there is practically no false information at the exit. As the probability of error decreases, the transmission rate increases, and the fidelity continues to remain at the specified level. Thus, the UOS system, as it were, adapts (adapts) to the state of the channel, using the channel as much as possible in each of its states.
In conclusion, we note the following fact, proved in information theory: in channels without memory, the presence of any feedback does not increase the throughput of the forward channel. Therefore, if the use of long codes is acceptable, then the feedback is not beneficial. However, as already indicated, long codes require very complex decoding devices, which are often practically impossible to implement. It is in this case that feedback can help, allowing you to realize the same bandwidth by simpler means.
Questions for Chapter 5
- What are the criteria for classifying codes?
- The source of independent messages has eight messages in its alphabet with probabilities P (A) = 0.3; P (B) = P (B) = 0.2; P (G) = 0.15; P (D) = 0.1; P (E) = 0.03; P (W) = P (I) = 0.01. Calculate the entropy of messages, construct a non-uniform code using the Feno method, and determine how close it is to optimal. Compare the required channel rates for the Feno code and for the uniform code.
- Why are short error-correcting codes not very effective?
- Can the same error correcting code be used in a detection system and an error correction system?
- In a binary erasure channel without memory (see Ch. 3, Fig. 3.7), the error probability is p = 0, and the erasure probability is p c> 0. Prove that a code with d> 1 allows you to correct all erased symbols in such a channel if the erasure multiplicity is q c. Let some code A of length n have an odd value d. We construct a new code B of length n + 1, adding to the previous code a check symbol equal to the sum (modulo 2) of all other symbols. Show that this increases d by 1.
- Show that the code B of length n + 1, constructed in the previous problem, allows you to correct errors with multiplicity q≤d / 2-1, i.e., the same ones that were corrected by code A and simultaneously detect errors of multiplicity d / 2, where d is even minimum code B distance.
- What code is dual to the simplest code (n, n-1) with one parity and d = 2? What is d for a dual code?
- When using the Hamming code (7,4) with the parity check (5.24), the sequence 1100111 is accepted. How should it be decoded by the Hamming algorithm? Same question if the sequence is 1100110? What if 1010001?
- The Hamming code (3,1) contains only two combinations: 000 and 111. Determine the equivalent error probability when using this code in a symmetric channel with independent errors occurring with probability p.
- The same code (3,1) is used in an asymmetric channel, in which P (1 → 0) = p, P (0 → 1) = 0. Suggest a reasonable decoding rule and calculate the equivalent error probability.
- Formula (5.28) contains four "checks for the symbol of the equidistant code (7,3). Taking into account that this code is cyclic, write down the checks for b 2 and b 3 and determine how the received sequences 0100110, 0110111, 0101010 will be decoded by the majority algorithm ?
- For two codes (6,5) and (4,3) with d = 2 for each, an iterative code is compiled. Find n, k and d for it and show how it allows you to "correct and detect errors?"
- * V binary system with information feedback (OPC), the errors are independent and their probability in the forward channel is pi = 0, l, and in the reverse channel, p 2 = 10 -5. 5-bit code combinations are used. Determine the probability of an undetected error and estimate the extent to which transmission is slowed down due to the detected errors.
- * In terms of question 13, p 1 = 0.5 (ie, there is no direct communication), and p 2 = 0. Is it possible to transfer information in this case? According to formula (5.33), the probability of an undetected error is p n.o = 0. On the other hand, intuition suggests that the transfer of information is impossible here. How can such a contradiction be explained?
Errors in channels are usually grouped, the state of the channel can be very different. Therefore, if we apply the correcting code in the SPI (information transmission system) without feedback, then with a significant error density it will be ineffective in noise immunity, and with a low error density it will be ineffective in transmission rate. Usually, the correcting code is calculated for a constant interference density, therefore, open-loop PTS is used in systems with a constant information delay time, and also if there is no reverse channel or its creation is impossible.
It is necessary that the redundancy introduced into the transmitted information be commensurate with the state of the discrete channel at each moment of time. For example, an increase in the number of errors must be associated with an increase in redundancy. Redundancy is introduced in the transmitter, and the state of the channel can be judged by the results of receiving information. To regulate
redundancy, it is necessary that the receiver informs the transmitter about the number of errors. Therefore, there is a feedback channel. ITS with a feedback channel are divided into systems with decision feedback (ROS), systems with information feedback (IOS) and systems with combined feedback (COS). In systems with POC, the receiver, having received the codeword and having analyzed it for errors, makes the final decision either to issue the codeword to the consumer, or to erase it and send a re-request signal via the reverse channel. Systems with POC are called over-demand systems or automatic error-request systems. If the codeword is received without errors, the receiver generates and sends an acknowledgment signal to the feedback channel. The transmitter, having received the confirmation signal, transmits the next code combination. The active role belongs to the receiver, and the decision signal generated by the receiver is transmitted via the feedback channel. In systems with an ITS, information about the code combinations (or their elements) arriving at the receiver is transmitted via the feedback channel before final processing and making a final decision. It is possible that the codeword is relayed from the receiver to the transmitter. Such systems are called relay systems. It is possible that the receiver generates special signals that have a smaller volume than the useful information, but characterize the quality of its reception. These signals are also fed back from the receiver to the transmitter. If the amount of information transmitted through the feedback channel (receipt) is equal to the amount of information in the message transmitted through the forward channel, then the IOS is called complete. If the information of the receipt reflects only some signs of the message, then the ITS is called shortened. The receipt received via the feedback channel is analyzed by the transmitter. Based on the analysis results, the transmitter makes a decision on the transmission of the next codeword or on the repetition of the previously transmitted combinations. After that, the transmitter transmits signaling signals about the adopted decision, and then the corresponding codewords. In accordance with the service signals received from the transmitter, the receiver either issues the accumulated codeword to the recipient, or erases it and stores it as newly transmitted. In systems with a shortened ITS, the load of the feedback channel is less, but the probability of errors is higher than in systems with a full ITS.
In systems with CBS, the decision to issue a codeword to the recipient or to retransmit it can be made both in the receiver and in the transmitter, and the OS channel can be used both for the transmission of the receipt and for the decision. Systems with OS are divided into systems with a limited and unlimited number of repetitions. With a limited number of repetitions, the probability of error is greater, but the delay time is shorter.
If the SPI with feedback discards information in rejected code combinations, then this system is without memory. Otherwise, a closed-loop IMS is called a memory system. OS systems are adaptive information transfer systems, since Channel transmission is automatically matched to specific signal conditions. Feedback channels are formed by frequency or time separation methods from transmission channels useful information... To protect against distortion of signals transmitted over the OS channel, correction codes, multiple and parallel transmissions are used. Numerous algorithms for operating systems with an OS are currently known. The most common among them are systems:
· ROS with waiting for the OS signal;
· ROS with unaddressed repetition and blocking of the receiver;
· ROS with targeted repetition.
Systems with waiting after transmitting a codeword either wait for a feedback signal, or transmit the same codeword, but the transmission of the next codeword begins only after receiving confirmation on the previously transmitted combination.
Blocking systems transmit a continuous sequence of code combinations in the absence of OS signals over the previous n combinations. After detecting errors in the (n + 1) th combination, the system output is blocked for the time of receiving n combinations, in the memory of the receiver PDS systems the n previously received combinations are erased and a re-request signal is sent. The transmitter repeats the transmission of the n most recently transmitted codewords.
In systems with OS, redundancy is entered into the transmitted information taking into account the state of the discrete channel. With the deterioration of the channel condition, the introduced redundancy increases, and vice versa, as the channel condition improves, it decreases.
Depending on the purpose of the OS, systems are distinguished:
with decisive feedback (ROS);
with information feedback (IOS);
with combined feedback (KOS).
In systems with POC, the receiver, having received the codeword and analyzing it for errors, makes the final decision to issue the combination to the consumer of information or to erase it and send a signal on the retransmission of this codeword via the reverse channel (re-interrogation). Therefore, POC systems are often referred to as over-demand systems, or automatic error request systems (ADR). If the codeword is received without errors, the receiver generates and sends an acknowledgment signal to the OS channel, having received it, the transmitter transmits the next codeword. Thus, in systems with POC, an active role belongs to the receiver, and the decision signals generated by it are transmitted via the return channel (hence the name - the decisive OS). The transmission from ROS is similar to a telephone conversation in conditions of poor audibility, when one of the interlocutors, having poorly heard any word or phrase, asks the other to repeat them again, and if audible, either confirms the fact of receiving information, or in any case does not ask for repetition.
In systems with ITS, information about the code combinations (or combination elements) arriving at the receiver is transmitted via the reverse channel before their final processing and making final decisions. When talking on the phone, a relay IOS is often used, when, in conditions of strong interference, they ask the interlocutor to repeat the transmitted message to make sure that he received it correctly. If the repetition is correct, the sender gives confirmation, and if it is incorrect, he repeats the message again. A special case of an ITS is a complete retransmission of code combinations or their elements arriving at the receiving side. The corresponding systems are called relay systems. The information (receipt) received via the OS channel is analyzed by the transmitter, and based on the results of the analysis, the transmitter makes a decision on the transmission of the next codeword or on the repetition of the previously transmitted ones. After that, the transmitter transmits signaling signals about the adopted decision, and then the corresponding codewords. In accordance with the service signals received from the transmitter, the receiver either issues the accumulated code combination to the recipient of information, or erases it and stores the newly transmitted one.
In systems with CBS, the decision to issue a codeword to the recipient of information or to retransmit it can be made both in the receiver and in the transmitter of the PDS system, and the OS channel is used to transmit both receipts and decisions.
Systems with OS are also subdivided into systems with a limited number of repetitions and with an unlimited number of repetitions. In systems with a limited number of repetitions, each code combination can be repeated no more than l times, and in systems with an unlimited number of repetitions, the transmission of combinations is repeated until the receiver or transmitter decides to deliver this combination to the consumer. With a limited number of repetitions, the probability of giving the recipient an incorrect combination is greater, but there is less time loss for transmission and easier implementation of the equipment. Note that in systems with an OS, the message transmission time does not remain constant and depends on the state of the channel.
Systems with OS can discard or use the information contained in rejected code combinations in order to make a more correct decision. Systems of the first type are called systems without memory, and the second - systems with memory.
The presence of errors in the OS channels leads to the fact that in systems with POC there are specific fidelity losses, consisting in the appearance of unnecessary code combinations - inserts, and the disappearance of code combinations - fallout... Insertions are obtained when the receiver sends a decision signal on the correctness of the received codeword, and in the OS channel it is transformed into a re-request signal. In this case, the transmitter repeats the previous codeword, and the receiver perceives it as the next one, i.e. the consumer is given the same code combination twice. Dropouts are obtained when the re-request signal generated by the receiver in the OC channel is transformed into a confirmation signal of the correct reception. In this case, the transmitter transmits the next codeword, and the previous one is erased by the receiver and is not received by the receiver.
Loss of fidelity due to errors in the OS channels is also possible in systems with ITS. In truncated IOS, such errors occur for reasons similar to those described above, when a receipt corresponding to a distorted signal in the OS channel is transformed into a receipt corresponding to an undistorted signal. As a result, the transmitter is unable to detect the fact of erroneous reception. In full IOS in the feedback channel, distortions are possible that fully compensate for distortions in the forward channel, as a result of which errors cannot be detected.
Numerous algorithms for operating systems with an OS are currently known. The most common among them are systems:
POC with waiting for OS signal;
POC with unaddressed repetition and blocking of the receiver;
ROS with targeted repetition.
Waiting systems after the transmission of the codeword, either a feedback signal is expected, or the same codeword is transmitted, but the transmission of the next codeword is started only after receiving confirmation of the previously transmitted combination.
Interlocking systems carry out transmission of a continuous sequence of code combinations in the absence of OS signals on the previous n combinations. After detecting errors in the (n + 1) -th combination, the system output is blocked for the time of receiving n combinations, n previously received combinations and a re-request signal is sent. Transmitter repeats transmission n last transmitted codewords.
Systems with targeted repetition It is distinguished by the fact that the code combinations with errors are marked with conditional numbers, in accordance with which the transmitter retransmits only these combinations.
In a system with POC, information combinations of length n single elements and decision commands, and through the feedback channel - service combinations. In a system with an ITS, information combinations of length k single elements and decision commands, and along the OS channel - check combinations of length n- k single elements.
Studies have shown that for a given transmission fidelity, the optimal code length in systems with ITS is slightly less than in systems with DFs, which makes the implementation of coding and decoding devices cheaper. However, the overall complexity of the implementation of systems with ITS is greater than that of systems with ROS. Therefore, POC systems have found wider application. Systems with ITS are used in cases where the reverse channel can be effectively used for transmitting receipts without prejudice to other purposes.
