Линейные коды

Размещено на http://www.allbest.ru/

Лекция

Линейные коды

Определение 1. Систематическими называются коды, в которых информационные и контрольные символы занимают строго определенные места в кодовых комбинациях.

Определение 2. Линейными называются коды, в которых контрольные символы представляют собой линейные комбинации информационных символов:

.

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

Определение 3. Весом кодового слова называется число его ненулевых элементов.

Отметим важное свойство групповых кодов: минимальное кодовое расстояние между кодовыми словами группового кода равно минимальному весу ненулевых кодовых слов.

Построение линейного кода осуществляется с помощью так называемой образующей (порождающей, производящей) матрицы.

При построении порождающей матрицы следует руководствоваться следующими правилами:

1) количество начальных кодовых слов должно быть равно числу информационных символов;

2) все начальные кодовые слова должны быть различны;

3) среди начальных кодовых слов не должно быть нулевого;

4) все начальные кодовые слова должны быть линейно независимыми;

5) количество единиц в каждой начальной кодовой комбинации должно быть не меньше ;

6) кодовое расстояние между любыми парами начальных кодовых слов должно быть не меньше .

Подобранные по этим правилам начальные кодовые слова записывают в виде образующей матрицы , содержащей строк и столбцов:

. 1)

Код, порожденный данной матрицей, называется -кодом.

Любую порождающую матрицу можно привести к так называемой левой канонической или приведенной ступенчатой форме

, (2)

где - единичная подматрица порядка , - проверочная подматрица, содержащая строк и столбцов.

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

Метод кодирования с помощью порождающей матрицы состоит в следующем: первая комбинация - нулевая, строки порождающей матрицы представляют собой комбинаций искомого кода, остальные комбинации находят суммированием всех возможных комбинаций строк порождающей матрицы.

Пример 1. С помощью порождающей матрицы построить систематический линейный код, способный исправлять одиночную ошибку при передаче 16 сообщений ().

Решение. Известно, что . Значит, и .

По табл. определяем число контрольных символов: .

Согласно правилу построения проверочной подматрицы количество единиц в строке должно быть не меньше, чем . Из трехэлементных комбинаций выбираем только те, в которых количество единиц больше или равно двум: 110, 101, 011, 111.

Строим порождающую матрицу

. (3)

Строки в проверочной матрице можно менять местами. При этом получим несколько вариантов порождающих матриц и, следовательно, несколько вариантов линейных кодов для рассматриваемого примера.

Алгоритм образования контрольных символов по известной информационной части может быть записан следующим образом:

. (4)

Контрольный символ представляет собой сумму информационных символов, соответствующих единицам первого столбца проверочной подматрицы , второй контрольный символ - сумму информационных символов, соответствующих единицам второго столбца проверочной подматрицы, и т.д.

Пример 2. Закодировать в линейном коде комбинацию четырехзначного двоичного кода 1100 (.

Решение. Число информационных символов . Из табл. 3.1 .

Порождающей матрицей может служить матрица (3) из примера 3. Тогда согласно (4)

Итак, искомая полная комбинация кода: 1100110.

Замечание. Пусть - информационные символы, тогда кодовое слово линейного кода может быть найдено по формуле

. (5)

Закодируем комбинацию 1100 по формуле (5):

.

Коррекция ошибок выполняется с помощью проверок

. (6)

Число проверок равно числу контрольных символов корректирующего кода .

В результате проверок образуется комбинация символов , называемая синдромом. Если вес синдрома равен нулю, то принятая комбинация считается безошибочной, в противном случае принятая комбинация содержит ошибку.

Исправление ошибок проводится по виду синдрома с помощью контрольной матрицы , которая состоит из двух подматриц: и единичной подматрицы -го порядка :

. (7)

Столбцы такой матрицы представляют собой значение синдрома для разряда, соответствующего номеру столбца матрицы .

Пример 3. Показать процесс исправления ошибки в произвольном разряде какой-либо кодовой комбинации корректирующего кода, построенного в примере 3.3.

Решение. Согласно принципу построения системы проверок (6) система проверок для построенного кода будет иметь вид

Строим контрольную матрицу :

.

Если разряды синдрома соответствуют первому столбцу матрицы , т.е. , , , то ошибка - в первом разряде принятой комбинации, если синдром имеет вид , что соответствует второму столбцу матрицы , то ошибка - во втором разряде, а синдром 001 соответствует ошибке в третьем контрольном разряде кодовой комбинации, и т.д.

Для проверки корректирующих свойств кода используем комбинацию под номером 7: 1010101.

Пусть произошел сбой в четвертом разряде, т.е. комбинация принята в следующем виде: 1011101.

Находим синдром:

Синдром 111 совпадает с четвертым столбцом контрольной матрицы, следовательно, в четвертом разряде символ следует заменить на обратный.

Замечание. Пусть - кодовое слово линейного кода, тогда синдром может быть найден по формуле

. (8)

Найдем синдром принятой комбинации по формуле (3.8):

.

Замечание. Кодирование возможно и с помощью контрольной матрицы: контрольный символ () равен сумме информационных символов, соответствующих единицам -й строки матрицы .

Код Хэмминга

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

Хэмминг предложил расположить столбцы контрольной матрицы так, чтобы номер -го столбца матрицы и номер разряда кодовой комбинации соответствовали двоичному представлению числа . Тогда синдром, найденный с помощью проверочных уравнений, будет двоичным представлением номера разряда кодовой комбинации, в которой возникла ошибка. Для этого контрольные символы должны находиться не в конце кодовой комбинации, а на номерах позиций, выбранных по закону , т.е. на номерах 1, 2, 4, 8, … . Таким образом, характерная особенность контрольной матрицы кода Хемминга состоит в том, что ее столбцами являются номера символов кодового слова в двоичном коде длины .

Пример 4. Построить код Хэмминга для одной из комбинаций четырехразрядного двоичного кода.

Решение. Поскольку , , значит, , .

Исходная комбинация из четырех информационных символов приобретает вид , где - контрольные символы; - информационные символы.

Строим контрольную матрицу : ее столбцами являются номера символов кодового слова в трехразрядном двоичном коде.

Замечание. Десятичное число можно представить в виде

,

где могут принимать два значения: 0 или 1.

Тогда - -разрядное двоичное представление числа .

Например, , значит, 001 - трехразрядное двоичное представление 1; 6 110, так как . Тогда

.

После перестановки столбцов, имеющих одну единицу, контрольная матрица примет вид

. (9)

Контрольные символы определяются формулами

(10)

Система проверок имеет вид

(11)

Замечание. При передаче по каналу связи в кодовом слове может возникнуть двойная и более ошибка. В этом случае синдром может принять любое значение, в том числе и нулевое. При этом произойдет исправление случайного символа. Для исключения такого автоматического исправления вводится еще один символ для проверки всей комбинации на четность. Кодовое расстояние увеличивается: .

Пример 5. Закодировать в коде Хэмминга комбинацию 1101.

Решение. По условию , следовательно, . Контрольными символами будут . Информационные символы: .

Для нахождения контрольных символов используем контрольную матрицу (3.9) из предыдущего примера.

Из системы (10)

Кодовое слово будет иметь вид 1010101.

Допустим, что при передаче возникла ошибка, и мы приняли неверную комбинацию: 1010111 (возникла ошибка в шестом разряде).

С помощью системы проверок (3.11) находим значения разрядов синдрома:

Синдром указывает на то, что в шестом разряде принятой комбинации произошла ошибка ().

Если бы нам понадобилось построить код и для проверки двойных ошибок, то необходимо было бы ввести еще один дополнительный нулевой разряд:

.

Получим код 01010101.

Пусть при передаче и возникновении ошибки код будет иметь вид 01010111.

Проверка в этом случае показала бы, что синдром равен 110, а проверка всей комбинации на четность =0+1+0+1+0+1+1+1=1. Это указывает на одиночную ошибку. Допускается автоматическое исправление ошибки.

Существует следующий алгоритм декодирования кода Хэмминга с кодовым расстоянием (табл. 3.2).

Таблица 3.2

Сети Хемминга

Для нечеткого поиска могут быть использованы широко известные алгоритмы и коды Хемминга. Коды Хемминга давно и успешно применяются при кодировании и декодировании информации, позволяя успешно восстановить утерянную пре передачи информацию.

Сети Хемминга так же активно используются для оптического распознавания символов (OСR).

Однако алгоритмы Хемминга могут быть применены не только в теории кодирования информации, но и в вопросах информационного поиска. Особенно эффективно коды Хемминга работают вместе с аппаратом нечеткой логики.

Коды Хемминга -- простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку [2].

Сети Хэмминга представляют собой одну из разновидностей нейронных сетей. Принцип работы сетей Хэмминга основан на определении расстояния Хэмминга между объектами и нахождении наиболее близкого.

Алгоритмы Хемминга в своей работе используют линейный код, который по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.

В процессе поиска и выдачи информации неизбежно возникают ошибки, поэтому контроль целостности данных и исправление ошибок -- важные задачи на многих уровнях работы с информацией.

Актуальной представляется задача разработки системы нечеткого поиска, которая может находить слово в списке, даже если оно искажено или содержит опечатки и пропущенные символы.

Для обнаружения ошибок в сетях Хемминга используют коды обнаружения ошибок, для исправления -- корректирующие коды.

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

Таким образом, алгоритмы Хэмминга могут быть использованы для поиска слов, которые в исходном запросе набраны с ошибками.

Предположим у нас на входе есть словарь и необходимо найти искомое слово в этом словаре, даже если оно было набрано с ошибкой. Для этого нужно сначала продумать и разработать систему кодирования символьной информации в вектора. Зададим для каждого символа его битовую маску:

А- 00001

Б - 10001

В - 10010

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

Однако необходимо учитывать одну особенность сетей Хемминга. Если при написании была опечатка или даже две, то алгоритм работает хорошо, но если был пропущен символ или добавлен лишний, то Хемингово расстояние может оказаться слишком большим. Для того, чтобы устранить этот недостаток, мы будем подавать на вход, как само искомое слово, так и это же слово, исключая по очереди по одному символу в каждой позиции и добавляя по одной букве в каждую позицию. Такой подход позволит найти практически все случаи ошибок - опечатка, пропуск символа, лишний символ.

Следует отметить, что, не смотря на большую эффективность кодов Хемминга, они не лишены определенных недостатков. Линейные коды, как правило, хорошо справляются с редкими и большими ошибками и опечатками [4]. Однако их эффективность при сравнительно частотных, но небольших ошибках менее высока.

Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических задач информационного поиска.

Размещено на Allbest.ru