抗噪声编码。
在数字通信和数据存储中，干扰是不可避免的，这会使传输的信息失真。 为了对抗错误，使用抗噪声编码-为原始消息添加冗余，这使得在接收端检测甚至纠正错误成为可能。
在本文中，我们将在实践中分析两种经典算法。:
-**汉明码（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-验证条件的有效性。 如果条件为false，则会引发错误。 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
下面的测试验证了在长度为5到15位的10个随机序列上，速度为1/2且限制长度为K=3的卷积码的操作。 对于每个序列:
- 使用以下方法对其进行编码
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.
我们在实践中学到了什么:
-汉明码对于具有罕见单一错误的通道简单有效。
-卷积码提供更大的灵活性，更适合连续数据流，但需要更复杂的解码。