Noise-resistant coding.
In digital communication and data storage, interference is inevitable, which can distort the transmitted information. To combat errors, noise–resistant coding is used - adding redundancy to the original message, which makes it possible to detect and even correct errors on the receiving side.
In this article, we will analyze two classical algorithms in practice.:
- Hamming code (7,4) is a simple block code that corrects a single error in a block of 7 bits.
- Convolutional code with a speed of 1/2 and a limit length of 3 is a continuous code with memory decoded by the Viterbi algorithm.
All the examples are implemented using automated tests using the built-in library Test. You can not only see the code, but also verify its correctness.
Test – this is a standard library. It provides simple macros for writing unit tests.:
@test– checks that the expression returnstrue.@testset– groups tests, gives them names, and outputs a summary.@test_throws– checks that an exception is being thrown.@test_broken/@test_skip– for temporarily broken or missed tests.
In our code, we actively use @testset and @test to automatically test the operation of encoders and decoders on a variety of examples. This allows you to quickly locate errors and be confident in the performance of algorithms.
using Test
Hamming Code
The Hamming code (7,4) converts 4 information bits into a 7-bit codeword. 3 verification bits are added, calculated using the formulas:
p1 = d1 ⊕ d2 ⊕ d4
p2 = d1 ⊕ d3 ⊕ d4
p3 = d2 ⊕ d3 ⊕ d4
The code word is formed in the following order: [p1, p2, d1, p3, d2, d3, d4]. This placement allows you to immediately determine the number of the erroneous bit based on the syndrome (the result of three parity checks).
@assert – verifies the validity of the condition. If the condition is false, an error is thrown. AssertionError with the specified message (if it has been transmitted).
function hamming_encode(data)
@assert length(data) == 4 "Для кода (7,4) требуется ровно 4 бита данных"
d1, d2, d3, d4 = data
p1 = xor(d1, d2, d4)
p2 = xor(d1, d3, d4)
p3 = xor(d2, d3, d4)
return [p1, p2, d1, p3, d2, d3, d4]
end
When decoding, the syndrome is calculated [s1, s2, s3]:
s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4
s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4
s3 = p3 ⊕ d2 ⊕ d3 ⊕ d4
Number error_pos = s1*1 + s2*2 + s3*4 indicates the position of the erroneous bit (from 1 to 7). If error_pos != 0, invert the bit at this position, then extract the information bits.
function hamming_decode(received)
@assert length(received) == 7 "Принятое слово должно иметь длину 7"
p1, p2, d1, p3, d2, d3, d4 = received
s1 = xor(p1, d1, d2, d4)
s2 = xor(p2, d1, d3, d4)
s3 = xor(p3, d2, d3, d4)
error_pos = s1*1 + s2*2 + s3*4
corrected = copy(received)
if error_pos != 0
corrected[error_pos] = xor(corrected[error_pos], 1)
end
data = [corrected[3], corrected[5], corrected[6], corrected[7]]
return data, corrected, error_pos
end
The test below verifies the correctness of the Hamming code (7,4) on all possible 16 input data variants (from 0 to 15) and on all possible single error positions (from 1 to 7). For each input vector:
- Encodes it into a code word.
- Verifies that decoding returns the original data, the code word itself, and the error position 0 without distortion.
- Then, for each of the 7 positions, artificially inverts a bit in the codeword and decodes the distorted version:
- the data must match the original ones.,
- the corrected word must match the original code word,
- the specific position of the error must match the number of the entered error.
@testset "Код Хэмминга (7,4) — все комбинации" begin
for n in 0:15
data = [Int((n >> i) & 1) for i in 0:3]
codeword = hamming_encode(data)
decoded, corrected, err_pos = hamming_decode(codeword)
@test decoded == data
@test corrected == codeword
@test err_pos == 0
for pos in 1:7
noisy = copy(codeword)
noisy[pos] = xor(noisy[pos], 1)
decoded, corrected, err_pos = hamming_decode(noisy)
@test decoded == data
@test corrected == codeword
@test err_pos == pos
end
end
end;
A total of 384 tests – all passed successfully. The code is guaranteed to correct any single error in the block and return the original data.
Convolutional code
Unlike block code, convolutional code works with a continuous stream of bits. It uses a shift register of length K=3 (the state is determined by the two previous bits) and two generating polynomials (in binary form 111 and 101, which corresponds to octal 7 and 5).
Two output bits are generated for each input bit.:
out1 = reg[1] ⊕ reg[2] ⊕ reg[3]
out2 = reg[1] ⊕ reg[3]
To complete the code, the following are added to the end of the sequence K-1 = 2 zero bits to clear the register.
const K = 3
const G1 = [1,1,1]
const G2 = [1,0,1]
function encode_conv(data)
tail = zeros(Int, K-1)
input = [data; tail]
reg = zeros(Int, K)
output = Int[]
for bit in input
reg = [bit; reg[1:end-1]]
out1 = xor(reg[1] & G1[1], reg[2] & G1[2], reg[3] & G1[3])
out2 = xor(reg[1] & G2[1], reg[2] & G2[2], reg[3] & G2[3])
push!(output, out1, out2)
end
return output
end
The Viterbi decoder finds the most probable sequence of transmitted bits using the principle of dynamic programming. For each time point (pairs of received bits) we calculate metrics (Hamming distances) for all possible states (there are 4 of them) and remember the best transitions. In the end, we choose the path with the minimum metric and restore the bits in the reverse pass.
function decode_conv(received)
n_steps = length(received) ÷ 2
num_states = 2^(K-1)
INF = 10^9
metrics = fill(INF, num_states)
metrics[1] = 0
prev_state = Vector{Vector{Int}}(undef, n_steps)
prev_bit = Vector{Vector{Int}}(undef, n_steps)
for step in 1:n_steps
r1 = received[2*(step-1)+1]
r2 = received[2*(step-1)+2]
new_metrics = fill(INF, num_states)
prev_state[step] = zeros(Int, num_states)
prev_bit[step] = zeros(Int, num_states)
for curr_state in 0:(num_states-1)
if metrics[curr_state+1] == INF
continue
end
for bit in 0:1
s1 = (curr_state >> 1) & 1
s2 = curr_state & 1
next_state = bit*2 + s1
reg = [bit, s1, s2]
out1 = xor(reg[1]&G1[1], reg[2]&G1[2], reg[3]&G1[3])
out2 = xor(reg[1]&G2[1], reg[2]&G2[2], reg[3]&G2[3])
dist = (out1 != r1) + (out2 != r2)
new_metric = metrics[curr_state+1] + dist
if new_metric < new_metrics[next_state+1]
new_metrics[next_state+1] = new_metric
prev_state[step][next_state+1] = curr_state
prev_bit[step][next_state+1] = bit
end
end
end
metrics = new_metrics
end
final_state = findmin(metrics)[2] - 1
bits = Int[]
state = final_state
for step in n_steps:-1:1
bit = prev_bit[step][state+1]
push!(bits, bit)
state = prev_state[step][state+1]
end
reverse!(bits)
data_len = n_steps - (K-1)
return bits[1:data_len]
end
The test below verifies the operation of a convolutional code with a speed of 1/2 and a limit length of K=3 on 10 random sequences of bits from 5 to 15 in length. For each sequence:
- Encodes it using
encode_conv. - Verifies that decoding completely restores the original data without distortion (
decoded == data - Introduces one random error (inverts one bit in the encoded sequence) and decodes. Verifies that the code corrects this error, and the recovered data matches the original data.
- Introduces two random errors in different positions and decodes. Since the correction of two errors is not guaranteed, it is only checked that the length of the recovered data matches the length of the original data (i.e., the algorithm continues to work and outputs the correct length).
@testset "Свёрточный код (скорость 1/2, K=3) — случайные данные" begin
using Random
Random.seed!(1234)
for test_idx in 1:10
len = rand(5:15)
data = rand(0:1, len)
encoded = encode_conv(data)
decoded = decode_conv(encoded)
@test decoded == data
noisy = copy(encoded)
err_pos = rand(1:length(noisy))
noisy[err_pos] = xor(noisy[err_pos], 1)
decoded2 = decode_conv(noisy)
@test decoded2 == data
noisy2 = copy(encoded)
pos1, pos2 = rand(1:length(noisy2), 2)
noisy2[pos1] = xor(noisy2[pos1], 1)
noisy2[pos2] = xor(noisy2[pos2], 1)
decoded3 = decode_conv(noisy2)
@test length(decoded3) == length(data)
end
end;
A total of 30 tests, all successfully completed.
Conclusion
We have implemented two fundamental noise-tolerant coding algorithms and confirmed their correctness using the built-in library. Test.
What we learned in practice:
- The hamming code is simple and effective for channels with rare single errors.
- Convolutional codes provide more flexibility and are better suited for continuous data streams, but require more complex decoding.