Кодер и декодер кода Хэмминга на VB.NET
Опубликовано: 24.08.2018
Коды Хемминга позволяют закодировать исходное сообщение таким образом, чтобы после передачи его по зашумлённым каналам связи (например, по радиоканалу) и искажениям в принятой информации, можно было восстановить исходное сообщение.
Код Хэмминга добавляет к сообщению (информационные разряды) некоторое количество избыточной информации (проверочные разряды), сформированной определённым образом. Сообщение с добавленной проверочной информацией называется «кодовый символ» или «кодовое слово». Параметры кода указываются, например, так: (7, 4). Это означает, что длина кодового слова равна 7 битам, а длина сообщения – 4 бита. В зависимости от количества информационных и проверочных разрядов в кодовых словах существуют коды Хэмминга (7,4), (9,5), (11, 7), (15, 11), (31, 26), (63, 57) и т. д.
Общий вид формулы, по которой определяются виды кодов Хэмминга по соотношению числа информационных символов к проверочным: (2x − 1, 2x − x − 1), где x – натуральное число.
Чтобы восстановить закодированное сообщение, оно подвергается декодированию. При этом есть вероятность, что исходное сообщение нельзя будет восстановить, в случае превышения числом ошибок корректирующей способности кода. Однако помехоустойчивость закодированной информации всё равно выше, чем у незакодированной.
Из-за своей простоты, кодирование кодом Хемминга получило широкое распространение. Оно применяется, например, в беспроводной технологии WiFi, в системах хранения данных (RAID-массивах), в некоторых типах микросхем памяти, в схемотехнике и т.д.
Хорошая статья, описывающая принцип работы кода Хэмминга, есть, например, на Хабре .
2 Кодер кода Хэмминга (15, 11), написанный на VB.NET
Напишем кодировщик, который будет получать на вход 11 бит данных, кодировать их и возвращать 15 бит выходной информации. Если на вход пришло больше 11-ти бит данных, генерируется исключение. Если данных меньше 11-ти бит (например, 1 байт – 8 бит), то число дополняется нулями в старших разрядах до 11-ти бит и далее кодируется обычным образом. Возвращает кодер 16 бит (кодовое слово).
Код кодера Хэмминга (15, 11) на VB.NET (разворачивается) ''' <summary> ''' Кодирует 11 бит информации кодом Хэмминга (15, 11). ''' Входные данные – 11 бит, выходные – 16 бит. ''' </summary> ''' <param name="dataIn">Входные данные, не более 11-ти бит.</param> ''' <remarks> ''' Размещение проверочных и информационных бит в кодовом слове: ''' ''' |15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00| ''' in_data | | | | | | L| K| I| H| G| F| E| D| C| B| A| ''' code_word| L| K| I| H| G| F| E| P| D| C| B| P| A| P| P| X| ''' ''' A,B,C,D,E,F,G,H,I,K,L – биты данных информационного слова; ''' P – проверочный бит; ''' X – бит, равный 0 (не используется). ''' Кодовое слово дополняется одним битом, чтобы длина была равна степени двойки. Сейчас этот бит никак не используется. ''' Можно его использовать как бит чётности и получить так называемый дополненный код Хэмминга. Здесь этого не сделано. ''' </remarks> Public Shared Function Encode_15_11(ByVal b As BitArray) As BitArray 'Можно также добавить проверку на длину передаваемой битовой последовательности: 'If (b.Count > 11) Then ' Throw New ArgumentException("Входная последовательность длиннее 11-ти битов.") 'End If Dim preDataIn As New BitArray(11) For i As Integer = 0 To 10 If (b.Count > i) Then preDataIn(i) = b(i) Else Exit For End If Next Dim dataIn As New BitArray(preDataIn) 'Весь процесс кодирования – это сложение по модулю два бит информационного слова. Dim codeWord As New BitArray(16) 'Младший разряд не используется. Можно добавить в него проверку на чётность. codeWord(0) = False 'Вычисление первого проверочного символа: codeWord(1) = dataIn(0) Xor dataIn(1) Xor dataIn(3) Xor dataIn(4) Xor dataIn(6) Xor dataIn(8) Xor dataIn(10) 'Вычисление второго проверочного символа: codeWord(2) = dataIn(0) Xor dataIn(2) Xor dataIn(3) Xor dataIn(5) Xor dataIn(6) Xor dataIn(9) Xor dataIn(10) 'Вычисление третьего проверочного символа: codeWord(4) = dataIn(1) Xor dataIn(2) Xor dataIn(3) Xor dataIn(7) Xor dataIn(8) Xor dataIn(9) Xor dataIn(10) 'Вычисление четвертого проверочного символа: codeWord(8) = dataIn(4) Xor dataIn(5) Xor dataIn(6) Xor dataIn(7) Xor dataIn(8) Xor dataIn(9) Xor dataIn(10) 'Информационные символы: codeWord(3) = dataIn(0) codeWord(5) = dataIn(1) codeWord(6) = dataIn(2) codeWord(7) = dataIn(3) codeWord(9) = dataIn(4) codeWord(10) = dataIn(5) codeWord(11) = dataIn(6) codeWord(12) = dataIn(7) codeWord(13) = dataIn(8) codeWord(14) = dataIn(9) codeWord(15) = dataIn(10) Return codeWord End FunctionДанный кодер легко переписать таким образом, чтобы он работал не с битовыми массивами типа BitArray(), а с байтами: на вход получал 11-разрядное число (от 0 до 0x7FF) и выдавал 2 закодированных байта:
Public Shared Function Encode_15_11(ByVal numberToEncode As Integer) As Byte() Dim enc As BitArray = Hamming.Encode_15_11(New BitArray({numberToEncode})) Dim encBytes(1) As Byte enc.CopyTo(encBytes, 0) Return encBytes End Function3 Декодер кода Хэмминга (15, 11), написанный на VB.NET
Теперь пора поговорить о декодере. Декодер плучает на вход 2 байта закодированных данных и возвращает 11 бит декодированных данных, которые распределены по двум байтам. Если в кодер были переданы 8 бит данных, то нас будет интересовать только первый байт, полученный с декодера.
Код декодера Хэмминга (15, 11) на VB.NET (разворачивается) ''' <summary> ''' Декодер кода (15, 11). ''' </summary> ''' <param name="b">Входные данные, 16 бит (2 байта).</param> ''' <returns>Выходные данные – 10 бит.</returns> ''' <remarks> ''' Размещение проверочных и информационных бит в кодовом слове: ''' ''' |15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00| ''' code_word| L| K| I| H| G| F| E| P| D| C| B| P| A| P| P| X| ''' out_data | | | | | | L| K| I| H| G| F| E| D| C| B| A| ''' ''' A,B,C,D,E,F,G,H,I,K,L – биты данных информационного слова; ''' P – проверочный бит; ''' X – бит, равный 0 (не используется). ''' ''' Кодовое слово дополняется одним битом, чтобы длина была равна степени двойки. Сейчас этот бит никак не используется. ''' Можно его использовать как бит четности и получить так называемый дополненный код Хэмминга. Здесь этого не сделано. ''' </remarks> Public Shared Function Decode_15_11(ByVal b As Byte()) As Integer Dim codeWord As New BitArray(b) '16 бит входных данных 'Весь процесс декодирования – это сложение по модулю два бит информационного слова, по весу полученных единиц в результате – получение позиции ошибки. Dim syndrome As New BitArray(4) 'Вычисление первого проверочного символа из полученного кодового слова и далее сравнение его с полученным. syndrome(0) = codeWord(3) Xor codeWord(5) Xor codeWord(7) Xor codeWord(9) Xor codeWord(11) Xor codeWord(13) Xor codeWord(15) Xor codeWord(1) 'Вычисление второго проверочного символа из полученного кодового слова и далее сравнение его с полученным. syndrome(1) = codeWord(3) Xor codeWord(6) Xor codeWord(7) Xor codeWord(10) Xor codeWord(11) Xor codeWord(14) Xor codeWord(15) Xor codeWord(2) 'Вычисление третьего проверочного символа из полученного кодового слова и далее сравнение его с полученным. syndrome(2) = codeWord(5) Xor codeWord(6) Xor codeWord(7) Xor codeWord(12) Xor codeWord(13) Xor codeWord(14) Xor codeWord(15) Xor codeWord(4) 'Вычисление четвёртого проверочного символа из полученного кодового слова и далее сравнение его с полученным. syndrome(3) = codeWord(9) Xor codeWord(10) Xor codeWord(11) Xor codeWord(12) Xor codeWord(13) Xor codeWord(14) Xor codeWord(15) Xor codeWord(8) 'Вычисление по синдрому позиции ошибки. Это просто ПЗУ или дешифратор. 'Если смотреть на синдром как на число - то это и есть номер позиции ошибки. 'Синдром равен 0 - ошибки нет. 'Поскольку на выход модуля передаются только биты данных - не все варианты перечислены, нет смысла исправлять проверочные биты. Dim syn As Integer = (Convert.ToInt32(syndrome(3)) End Function4 Консольная программа, кодирующая и декодирующая код Хемминга (15, 11)
Для быстрой проверки кодировщика и декодировщика кода Хэмминга (15, 11), используя вышеописанные классы, я написал две программы. Первая – кодер Хэмминга . Вводите 11-разрядное число (от 0 до 0x7FF или 2047), и на выходе получаем 16-разрядное число, представленное в виде двух байтов.
Внешний вид программы кодера кода Хэмминга (15, 11)
Вторая программа – декодер кода Хмминга (15, 11) .
Внешний вид программы декодера кода Хэмминга (15, 11)
Легко убедиться, что если мы внесём битовую ошибку при декодировании, то декодер восстановит исходное закодированное число.
Обе программы работают под ОС Windows и требуют .NET версии 3.5 . Выкладываю описанные программы.