We transmit a message from one end of the channel to the other. After being subjected to interference from noise, the message arriving at the other end of the channel may have changed significantly. To ensure that the message can still be identified after passing through the channel, we need to process the message before transmission.
For example, let’s assume there’s a channel with a 10% chance of flipping a bit from 0 to 1 or 1 to 0. In that case, any sufficiently long message we send will likely contain errors. To avoid errors, we can repeat each bit three times. For instance, if the original message to be transmitted is 101, we can transform it into 111 000 111. So, even if there’s an error in one bit, causing the other end of the channel to receive 111 010 111, the receiver can still discern that the original message was 111 000 111, thus deducing 101.
In previous articles, we discussed source encoding, using Huffman coding as an example. The aim was to simplify the message to be transmitted as much as possible. Note that source encoding and channel encoding are entirely different concepts. Source encoding encodes the message to represent it more efficiently, while channel encoding adds new bits to make the message resistant to noise. These two techniques are not mutually exclusive; we can perform source encoding followed by channel encoding on a set of messages.
Below shows a transmission model，it can be noticed that the places of source coding and channel coding are different.
In the upcoming articles, we will introduce how to perform channel encoding. This article assumes that the signals have already been encoded. First, let’s examine what happens to the signals as they pass through the channel. Before that, we need to introduce some new terms.
Hamming weight represents the number of non-zero symbols in a string of symbols. For example, if a = 1001, then the Hamming weight of a is 2, denoted as wt(a) = 2.
Hamming distance represents the number of different symbols at the same position in two strings of symbols. For example, if a = 1001 and b = 1100, we can see that symbols at the second and fourth positions in a and b are different. Therefore, their Hamming distance is 2, denoted as d(a, b) = 2.
Suppose there are several symbols. We compare each pair of symbols and find the Hamming distance between each pair. Among these distances, the smallest one is called the Minimum Hamming Distance (d). We can imagine these symbols as points represented on a graph as C1, C2, etc. At least one pair of symbols will have a distance of d between them, and the distances between the remaining symbols will be greater than or equal to d.
If we pass any symbol through a channel with noise e, the noise will affect the symbol, and the receiver will receive a result 𝑟=𝑐+𝑒. In this case, unless 𝑤𝑡(𝑒)=0, meaning the noise is zero, 𝑟 will deviate from c, indicating interference from noise.
Is there a scenario where noise could exactly change one symbol into another, leading to misinterpretation? The answer is yes. If 𝑤𝑡(𝑒)=𝑑, it is possible. We just mentioned that the difference between two symbols is at least d. If 𝑤𝑡(𝑒)≤𝑑−1, it’s impossible to transform 𝐶1 into C2. For example, let’s take 𝐶1=11011 and 𝐶2=01010 with 𝑑(𝐶1,𝐶2)=2. To transform 𝐶1+𝑒 into 𝐶2, where 𝑒=10001, we have 𝑤𝑡(𝑒)=2=𝑑(𝐶1,𝐶2).
In other words, if the channel has noise and 𝑤𝑡(𝑒)≤𝑑−1, we can detect judgment errors. Drawing circles with each symbol as the center and a radius of 𝑑−1 allows us to determine the error-detection range. In other words, we can detect a maximum of 𝑑−1 erroneous bits.
However, if 𝑟 falls within the overlapping area of the circles, we will be unable to determine the original symbol. For example, from the r in the diagram below, we cannot determine whether the symbol is ultimately 𝐶1 or 𝐶2.
If the range of 𝑤𝑡(𝑒) is even smaller, is it possible not only to detect errors but also to restore the original symbol? Consider why we currently cannot determine the original symbol: it’s because r falls between at least two circles. If 𝑤𝑡(𝑒) is smaller, making the radius of the circles smaller so that none of the circles overlap, then not only can we detect errors, but we can also restore the original symbol.
Given that the shortest distance between centers of circles is 𝑑, to prevent overlapping, we say
In this way, as long as we observe where 𝑟 falls within which circle, the center of that circle is the symbol we want to transmit. In other words, if we have noise in a channel
Then we can always detect and correct errors. For example, with a set of symbols where 𝑑=7, we can correct up to 3 erroneous bits.
Assuming there is a Binary Symmetric Channel (BSC), where both the input and output can only be 0 or 1. During transmission, there is a probability 𝑝 of transforming 0 into 1 and 1 into 0, as shown in the diagram below.
After passing through the channel, the output of the decoder can have three possibilities:
- Correct Decoding: Output the symbol originally transmitted (e.g., C1).
- Decoding Error: Output a symbol, but it’s not the original symbol.
- Decoding Failure: Output a symbol that doesn’t exist.
Given that we can correct floor((𝑑−1)/2) errors, we can calculate the probability of errors occurring. The sum of the probabilities of decoding error and decoding failure is termed the Block error probability. Assuming a symbol length of 𝑛, after passing through the channel, if there are only floor((𝑑−1)/2) or fewer bit errors, they can be directly corrected. Therefore, we only need to sum the probabilities of more than floor((𝑑−1)/2) bit errors occurring. Thus, the Block error probability is as follows (note that this probability is an upper bound, considering the worst-case scenario).
In which：
This article introduced the basic concepts of error detection and correction. In the next article on channel encoding, we will explore how Channel Encoder and Channel Decoder perform encoding to generate resistance to channel noise.
