Рейтинг@Mail.ru

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

Print Friendly, PDF & Email

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

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

Код Хэмминга добавляет к сообщению (информационные разряды) некоторое количество избыточной информации (проверочные разряды), сформированной определённым образом. Сообщение с добавленной проверочной информацией называется «кодовый символ» или «кодовое слово». Параметры кода указываются, например, так: (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 Function

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

Вторая программа – декодер кода Хмминга (15, 11).

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

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

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

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

Last modified onПонедельник, 17 Февраль 2020 12:00 Read 34382 times

Поблагодарить автора:

Поделиться

Print Friendly, PDF & Email