Рейтинг@Mail.ru

Кодер и декодер кода Хэмминга на VB.NET

1Что такое код Хэмминга

Коды Хемминга позволяют закодировать исходное сообщение таким образом, чтобы после передачи его по зашумлённым каналам связи (например, по радиоканалу) и искажениям в принятой информации, можно было восстановить исходное сообщение. Код Хэмминга добавляет к сообщению некоторое количество избыточной информации, сформированной определённым образом. Чтобы восстановить закодированное сообщение, оно подвергается декодированияю. При этом есть вероятность, что исходное сообщение нельзя будет восстановить, в случае превышения числом ошибок корректирующей способности кода, однако помехоустойчивость всё равно выше, чему у незакодированной информации.

Из-за своей простоты, кодирование кодом Хемминга получило широкое распространение. Оно применяется, например, в беспроводной технологии WiFi, в системах хранения данных (RAID-массивах), в некоторых типах микросхем памяти, в схемотехнике и т.д.

Хорошая статья, описывающая принцип работы кода Хэмминга, есть, например, на Хабре.

2Кодер кода Хэмминга (15, 11), написанный на VB .NET

Определим пространство имён Hamming, и создадим в нём метод Encode_15_11(), который будет получать на вход 11 бит данных, кодировать их и возвращать 15 бит (на самом деле 16) выходной информации (кодовое слово). Если на вход пришло больше 11-ти бит данных, генерируется исключение. Если данных меньше 11-ти бит, то число дополняется нулями в старших разрядах и далее кодируется обычным образом.

Код кодера Хэмминга (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 Function

Кстати, если мы напрямую преобразуем тип Integer в BitArray, то длина битового массива будет равна 32-м битам. Передача 32-битового массива в метод Encode_15_11() вызовет исключение. Так что здесь необходимо предусмотреть урезание числа до 11-ти разрядов. Я опустил это для того чтобы не захламлять код второстепенными действиями.

3Декодер кода Хэмминга (15, 11), написанный на VB .NET

Теперь пора поговорить о декодере. Декодер плучает на вход 2 байта закодированных данных и возвращает 11 бит декодированных данных, которые распределены по двум байтам. Если в кодер были переданы 8 бит данных, то нас будет интересовать только первый байт, полученный с декодера.

Код декодера Хэмминга (15, 11) на VB.NET (разворачивается)
''' <summary>
''' Декодер кода Хэмминга (15, 11). 
''' </summary>
''' <param name="b">Входные данные.</param>
''' <returns>Выходные данные – 32-битное число, значимые биты которого с 0 по 11.</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)) << 3) Or (Convert.ToInt32(syndrome(2)) << 2) Or (Convert.ToInt32(syndrome(1)) << 1) Or Convert.ToInt32(syndrome(0))

    '         |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|
    'Синдромы ошибок в информационных битах, позиции в кодовом слове 3,5,6,7,9,10,11,12,13,14,15:
    Dim correction As New BitArray(11) 
    Select Case syn
        Case 3 'позиция 3
            correction = New BitArray({True, False, False, False, False, False, False, False, False, False, False}) 
        Case 5 'позиция 5
            correction = New BitArray({False, True, False, False, False, False, False, False, False, False, False}) 
        Case 6 'позиция 6
            correction = New BitArray({False, False, True, False, False, False, False, False, False, False, False}) 
        Case 7 'позиция 7
            correction = New BitArray({False, False, False, True, False, False, False, False, False, False, False}) 
        Case 9 'позиция 9
            correction = New BitArray({False, False, False, False, True, False, False, False, False, False, False}) 
        Case 10 'позиция 10
            correction = New BitArray({False, False, False, False, False, True, False, False, False, False, False})  
        Case 11 'позиция 11
            correction = New BitArray({False, False, False, False, False, False, True, False, False, False, False})  
        Case 12 'позиция 12
            correction = New BitArray({False, False, False, False, False, False, False, True, False, False, False})  
        Case 13 'позиция 13
            correction = New BitArray({False, False, False, False, False, False, False, False, True, False, False})  
        Case 14 'позиция 14
            correction = New BitArray({False, False, False, False, False, False, False, False, False, True, False})  
        Case 15 'позиция 15
            correction = New BitArray({False, False, False, False, False, False, False, False, False, False, True})  
        Case Else
            'Если синдром равен 0 или указывает на ошибку в проверочном символе "P" – коррекция информационных символов не требуется.
            'Мы инициализировали correction() нулями (correction = New BitArray(11)), поэтому ничего делать не нужно.
        End Select

        'Результат декодирования с учетом коррекции (11 бит выходных данных):
        Dim outData As New BitArray(11)
        outData(0) = codeWord(3) Xor correction(0)    
        outData(1) = codeWord(5) Xor correction(1)     
        outData(2) = codeWord(6) Xor correction(2)     
        outData(3) = codeWord(7) Xor correction(3)     
        outData(4) = codeWord(9) Xor correction(4)     
        outData(5) = codeWord(10) Xor correction(5)   
        outData(6) = codeWord(11) Xor correction(6)  
        outData(7) = codeWord(12) Xor correction(7) 
        outData(8) = codeWord(13) Xor correction(8) 
        outData(9) = codeWord(14) Xor correction(9) 
        outData(10) = codeWord(15) Xor correction(10) 

        Dim masks(31) As Integer
        masks(0) = BitVector32.CreateMask()
        For i As Integer = 1 To 31
            masks(i) = BitVector32.CreateMask(masks(i - 1))
        Next

        Dim v As New BitVector32
        For i As Integer = 0 To 10
            v(masks(i)) = outData(i)
        Next
        Dim decoded As Integer = v.Data

        Return decoded

End Function

4Консольная программа, реализующаякодер и декодер кода Хемминга (15, 11)

Для быстрой проверки кодировщика и декодировщика кода Хэмминга (15, 11), используя вышеописанные классы, я написал две программы. Первая – кодер Хэмминга. Вводите 11-разрядное число (от 0 до 0x7FF или 2047), и на выходе получаем закодированное 16-разрядное число, представленное в виде двух байтов.

Внешний вид программы кодера кода Хэмминга (15, 11)
Внешний вид программы кодера кода Хэмминга (15, 11)

Да, кстати. Я не сделал в кодировщике проверку на верхнюю и нижнюю границы допустимых чисел. Следите, чтобы вводимое число лежало в диапазоне 0…2047, иначе получите неверное значение.

Вторая программа – декодер кода Хмминга (15, 11). Вводим через пробел два байта закодированных кодом Хемминга данных, и получаем декодированное число:

Внешний вид программы декодера кода Хэмминга (15, 11)
Внешний вид программы декодера кода Хэмминга (15, 11)

Легко убедиться, что если мы внесём битовую ошибку в закодированные данные, то при декодировании декодер восстановит исходное закодированное число:

Восстановление битовых ошибок декодером кода Хэмминга (15, 11)
Восстановление битовых ошибок декодером кода Хэмминга (15, 11)

Как видно, исходное число 14310 после кодирования даёт два байта {23810, 1710} = EE1116 = 11101110000100012. При внесении битовой ошибки в любом разряде декодер компенсирует её и возвращает исходное число 14310.

Обе программы работают под ОС Windows и требуют .NET версии 3.5. Выкладываю описанные программы.

Скачать кодер и декодер кода Хэмминга (15, 11)

Последнее изменениеВоскресенье, 01 Апрель 2018 17:21
(1 Голосовать)
Прочитано 328 раз

Поделиться

1 Комментарий

  • Andy
    Andy 01.04.2018 17:54 Комментировать

    Интересно. А как сделать кодер и декодер Хэмминга для других случаев, кроме (11, 15)?

Оставить комментарий