Помехоустойчивое кодирование.
В цифровой связи и хранении данных неизбежны помехи, которые могут исказить передаваемую информацию. Для борьбы с ошибками применяют помехоустойчивое кодирование – добавление избыточности в исходное сообщение, позволяющее обнаружить и даже исправить ошибки на приёмной стороне.
В этой статье мы на практике разберём два классических алгоритма:
- Код Хэмминга (7,4) – простой блочный код, исправляющий одиночную ошибку в блоке из 7 бит.
- Свёрточный код со скоростью 1/2 и длиной ограничения 3 – непрерывный код с памятью, декодируемый алгоритмом Витерби.
Все примеры реализованы используют автоматические тесты с использованием встроенной библиотеки Test. Вы сможете не только увидеть код, но и убедиться в его корректности.
Test – это стандартная библиотека. Она предоставляет простые макросы для написания модульных тестов:
@test– проверяет, что выражение возвращаетtrue.@testset– группирует тесты, даёт им имена и выводит сводку.@test_throws– проверяет, что выбрасывается исключение.@test_broken/@test_skip– для временно сломанных или пропущенных тестов.
В нашем коде мы активно используем @testset и @test, чтобы автоматически проверить работу кодеров и декодеров на множестве примеров. Это позволяет быстро локализовать ошибки и быть уверенным в работоспособности алгоритмов.
using Test
Код Хэмминга
Код Хэмминга (7,4) преобразует 4 информационных бита в 7-битное кодовое слово. Добавляются 3 проверочных бита, вычисляемых по формулам:
p1 = d1 ⊕ d2 ⊕ d4
p2 = d1 ⊕ d3 ⊕ d4
p3 = d2 ⊕ d3 ⊕ d4
Кодовое слово формируется в порядке: [p1, p2, d1, p3, d2, d3, d4]. Такое размещение позволяет по синдрому (результату трёх проверок на чётность) сразу определить номер ошибочного бита.
@assert – проверяет истинность условия. Если условие ложно, выбрасывается ошибка AssertionError с указанным сообщением (если оно передано).
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
При декодировании вычисляется синдром [s1, s2, s3]:
s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4
s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4
s3 = p3 ⊕ d2 ⊕ d3 ⊕ d4
Число error_pos = s1*1 + s2*2 + s3*4 указывает позицию ошибочного бита (от 1 до 7). Если error_pos != 0, инвертируем бит на этой позиции, затем извлекаем информационные биты.
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
Тест ниже проверяет корректность кода Хэмминга (7,4) на всех возможных 16 вариантах входных данных (от 0 до 15) и на всех возможных позициях одиночной ошибки (от 1 до 7). Для каждого входного вектора:
- Кодирует его в кодовое слово.
- Проверяет, что декодирование без искажений возвращает исходные данные, само кодовое слово и позицию ошибки 0.
- Затем для каждой из 7 позиций искусственно инвертирует бит в кодовом слове и декодирует искажённую версию:
- данные должны совпасть с исходными,
- исправленное слово должно совпасть с исходным кодовым словом,
- определённая позиция ошибки должна совпасть с номером внесённой ошибки.
@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;
Итого 384 теста – все пройдены успешно. Код гарантированно исправляет любую одиночную ошибку в блоке и возвращает исходные данные.
Свёрточный код
В отличие от блочного кода, свёрточный код работает с непрерывным потоком бит. Он использует сдвиговый регистр длиной K=3 (состояние определяется двумя предыдущими битами) и два порождающих полинома (в двоичном виде 111 и 101, что соответствует восьмеричным 7 и 5).
На каждый входной бит формируются два выходных бита:
out1 = reg[1] ⊕ reg[2] ⊕ reg[3]
out2 = reg[1] ⊕ reg[3]
Для завершения кода в конец последовательности добавляются K-1 = 2 нулевых бита, чтобы очистить регистр.
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
Декодер Витерби находит наиболее вероятную последовательность переданных бит, используя принцип динамического программирования. Для каждого момента времени (пары принятых бит) мы вычисляем метрики (расстояния Хэмминга) для всех возможных состояний (их 4) и запоминаем лучшие переходы. В конце выбираем путь с минимальной метрикой и восстанавливаем биты обратным проходом.
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
Тест ниже проверяет работу свёрточного кода со скоростью 1/2 и длиной ограничения K=3 на 10 случайных последовательностях бит длиной от 5 до 15. Для каждой последовательности:
- Кодирует её с помощью
encode_conv. - Проверяет, что декодирование без искажений полностью восстанавливает исходные данные (
decoded == data). - Вносит одну случайную ошибку (инвертирует один бит в закодированной последовательности) и декодирует. Проверяет, что код исправляет эту ошибку, и восстановленные данные совпадают с исходными.
- Вносит две случайные ошибки в разных позициях и декодирует. Поскольку исправление двух ошибок не гарантируется, проверяется только то, что длина восстановленных данных совпадает с длиной исходных (т.е. алгоритм продолжает работать выдаёт корректную длину).
@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;
Итого 30 тестов – все успешно пройдены.
Вывод
Мы реализовали два фундаментальных алгоритма помехоустойчивого кодирования и подтвердили их корректность с помощью встроенной библиотеки Test.
Что мы узнали на практике:
- Код Хэмминга прост и эффективен для каналов с редкими одиночными ошибками.
- Свёрточные коды дают большую гибкость и лучше подходят для непрерывных потоков данных, но требуют более сложного декодирования.