Я отошел от среды, последнюю версию можно найти по адресу: https://www.avoggu.com/posts/an-efficient-algorithm-for-hamming-(74)-decoding-matlab-implementation/
Пристегнитесь. Мы собираемся исследовать коды Хэмминга (7, 4) и эффективно реализовать их в Matlab / Octave.
Когда данные передаются по каналу, ошибки часто возникают из-за шума и других причин. Для учета потерь к фактическим данным добавляются и передаются избыточные данные. Эти данные могут использоваться для обнаружения и до некоторой степени исправления ошибок. Это известно как канальное кодирование, и коды Хэмминга являются примером.
Коды Хэмминга (7, 4) кодируют 4 бита данных в 7-битные блоки. Дополнительные 3 бита - это избыточные биты четности, о которых мы говорили.
Например, рассмотрим 4 бита данных: d1 d2 d3 d4. При этом биты четности рассчитываются как
p1 = d2 + d3 + d4 p2 = d1 + d3 + d4 p3 = d1 + d2 + d4
Все это объединено и закодировано как
p1 p2 p3 d1 d2 d3 d4
На стороне получателя снова создаются биты четности, которые проверяются с полученными битами для обнаружения и исправления ошибок.
Предположим, произошла только 1 ошибка, а значение бита было изменено. Если перевернуть d1, это вызовет разногласия в p2 и p3. И так далее.
Также обратите внимание, что ошибки могут возникать и в битах четности. Если только p1 не согласен, ошибка произошла в p1.
Конечно, это не сработает, если будет более одной ошибки. Но если ваш канал дает 2 ошибки на каждые 7 бит, вам все равно обречено. Типичные вероятности ошибок имеют порядок 10^-6.
Хорошо. Приступим к реализации. Вы могли заметить, что кодирование можно представить как умножение матриц.
data = [d1 d2 d3 d4]
|0 1 1 1 0 0 0|
encoded_data = [d1 d2 d3 d4] * |1 0 1 0 1 0 0|
|1 1 0 0 0 1 0|
|1 1 1 0 0 0 1|
Первым элементом результирующей матрицы будет d1*0 + d2*1 + d3*1 + d4*1. Превосходно! Это именно то, что мы хотели для бита четности p1.
Последние четыре бита будут самими битами данных.
Такая матрица называется generator matrix. Мы сгенерировали коды Хэмминга, умножив наши данные на матрицу генератора.
Обратное - decoder matrix. На стороне получателя мы используем его, чтобы определить, где произошла ошибка. Вот матрица декодера для кодов Хэмминга (7, 4).
|1 0 0 0 1 1 1| |0 1 0 1 0 1 1| * [p1 p2 p3 d1 d2 d3 d4] |0 0 1 1 1 0 1|
Умножив наш 7-битный код на эту матрицу, у нас останутся 3 бита, которые сообщают нам, произошла ли и где произошла ошибка.
Изучите, что делает матрица декодера. Первый элемент будет
p1 + d2 + d3 + d4. Это равно 2 * (d2 + d3 + d4). Поскольку это двоичный файл, у нас останется 0. Но если где-то произошла ошибка, сумма будет 1.
Вот как будет выглядеть результирующая матрица для ошибок в разных положениях.
No errors -> [0 0 0] Error in p1 -> [1 0 0] Error in p2 -> [0 1 0] Error in p3 -> [0 0 1] Error in d1 -> [0 1 1] Error in d2 -> [1 0 1] Error in d3 -> [1 1 0] Error in d4 -> [1 1 1]
Теперь, когда мы знаем, где ошибка, при декодировании просто переворачивается бит ошибки и удаляются биты четности.
Кодировка в Matlab (полный код в конце)
function [output_vector] = sevenFourHammingEncode(input_vector)
output_vector = [];
number_of_windows = length(input_vector) / 4; % assumes length to be multiple of four
four_bit_windows = reshape(input_vector, 4, number_of_windows)';
% p1 p2 p3 d1 d2 d3 d4
generator_matrix = [
0 1 1 1 0 0 0 ;
1 0 1 0 1 0 0 ;
1 1 0 0 0 1 0 ;
1 1 1 0 0 0 1 ;
];
output_vector = mod(four_bit_windows * generator_matrix, 2);
output_vector = reshape(output_vector', numel(output_vector), 1)';
end
Расшифровка
Извините за отсутствие комментариев. Когда я писал это, я не осознавал их важности. А теперь не помню, что он делает. Попробуйте представить код как матричные операции на бумаге, и вы поймете. Если да, напишите мне, и я добавлю его сюда. Спасибо :)
function [output_vector] = sevenFourHammingDecode(input_vector)
output_vector = [];
number_of_windows = numel(input_vector) / 7;
seven_bit_windows = reshape(input_vector, 7, number_of_windows)';
% p1 p2 p3 d1 d2 d3 d4
decoder_matrix = [
1 0 0 0 1 1 1 ;
0 1 0 1 0 1 1 ;
0 0 1 1 1 0 1 ;
];
% [ 1 0 0 ; 0 1 0 ; 0 0 1; 0 1 1 ; 1 0 1 ; 1 1 0 ; 1 1 1; ]
% [4, 2, 1, 3, 5, 6, 7]
result_vector = mod(decoder_matrix * seven_bit_windows', 2)';
result_vector = result_vector * [4 ; 2 ; 1]; % summing all elements
result_vector(result_vector == 4) = 9;
result_vector(result_vector == 1) = 11;
result_vector(result_vector == 3) = 12;
result_vector = mod(result_vector, 8);
seven_bit_windows = [ones(size(seven_bit_windows, 1), 1) seven_bit_windows]; % adding 1 column at start
result_vector = [(0:8:rows(result_vector)*8-1)' result_vector];
result_vector = result_vector * [1 ; 1]; % summing row and column
padded_data = reshape(seven_bit_windows', numel(seven_bit_windows), 1)';
padded_data(result_vector' + 1) = not(padded_data(result_vector' + 1));
padded_data = reshape(padded_data, 8, numel(padded_data) / 8)';
padded_data = padded_data(:, 5:end);
output_vector = reshape(padded_data', numel(padded_data), 1)';
end
При декодировании используются только матричные операции, и поэтому оно намного быстрее, чем при использовании for loop. На порядки быстрее.
Вот сценарий для сравнения производительности кодировок (3, 1), (5, 1) и Хэмминга (7, 4).
Вот и все. Раздел комментариев, если вам нужна помощь.
Aravind
