Блочные коды. Методика матричного кодирования.
Толстиков А.В. ПАМ
Курс3.Семестр5.Лекция2.Тема. Основы теории групповых кодов.
1. Основные понятия передачи информации. Кодирование и декодирование.
2. Блочные коды. Методика матричного кодирования.
3. Групповые коды. Таблица декодирования.
4. Коды Хэмминга.
Биргоф Г., Барти Т., c.236-257
Кодирование это преобразование информации из одного вида в другой. Оно проникло во все информационные технологии:
представление данных произвольной природы (чисел, текста, графики и т.п.) в памяти компьютера;
защита информации от несанкционированного доступа;
обеспечение помехоустойчивости при передачи информации по каналам связи;
сжатие информации в базах данных.
Обратная функция F -1, если она существует называется декодированием.
В общем виде задачу кодирования можно сформулировать следующим образом: при заданных алфавитах A, B и множестве S¢ сообщений найти такое кодирование, которое обладает определенными свойствами.
Критерий оптимальности, минимизация длины кодовых слов при выполнении определенных характеристических свойств. Свойства, которыми должны обладать кодирования можно отнести к одному из следующих:
помехоустойчивость или исправления ошибок;
заданная сложность или простота кодирования и декодирования.
Два слова и длины называются равными, если равны их все соответствующие символы:
Доказательство следует из того, что каждый символ ai в слове a может принимать ровно два значения 0 и 1.
Теорема 2. Множество Bn всех слов длины n с элементами из Z2 аддитивная абелева группа порядка 2n относительно операции побуквенного сложения слов по модулю 2.
Теорема 3. Множество Bn всех слов длины n с элементами из Z2 векторное пространство размерности n над полем Z2 относительно операции побуквенного сложения слов по модулю 2 и умножения на элементы из Z2.
Теорема 4. Расстояние d(a, b) между словами длины n с элементами из Z2 равно весу разности этих слов, т.е
d(a, b) = w(a – b).
Доказательство.Доказательство утверждения следует из того, что в поле Z2разность ai – bi элементов ai , bi равна 1 тогда и только тогда, когда ai ¹ b i. Тогда число единиц в разности равно числу попарно различных букв в словах a и b, т.е. равна весу разности.
Пример 1. Пусть a = 10111001, b = 00110011 слова длины 8. Тогда w(a) = 5, w(b) = 4, d(a, b) = 3,a-b = 10001010,
Все слова длины n можно геометрически интерпретировать как вершины n- мерного гиперкубам, а тогда минимальное число ребер разделяющее вершины a и b гиперкуба равно расстоянию Хемминга d(a, b)между соответствующими словами.
Рассматриваем проблему передачи информации по каналу связи (радиоканалы, оптико-волоконные каналы, линии связи, связи компьютера с периферийными устройствами), в котором могут возникать различные помехи. Практически все каналы связи не идеальны, так как любой сигнал с некоторой ненулевой вероятностью может быть принят неправильно. При цифровой обработке информации обычно передаются слова, которые являются символами 0 и 1. Если передаваемые сообщения являются длинными, то незначительная вероятность ошибки на один символ может привести к значительным искажениям посылаемого сообщения. Отметим, что при передачах сигналов по спутниковым средствам связи на них действуют внешние электромагнитные сигналы, космические лучи, внешние поля, и поэтому сигналы могут отразиться и измениться до неузнаваемости.
Рассмотрим простейшую схему канала связи (Рис. 3).
1) На вход канала поступает передаваемое сообщение (слово a) .
2) Слово кодируется устройством (функцией Е) в передаваемое кодированное сообщение (кодовое слово b).
3) Кодированное сообщение (кодовое слово b) передается по линии связи и при передаче по каналу связи на его действуют искажения, возникающие в линии связи и внешние помехи.
4) При выходе с линии связи получаем искаженное принятое сообщение (слово b’).
5) Слово декодируется устройством (функцией D), которая должна обнаруживать и исправлять ошибки, возникшие при передаче сообщения, на выходе получаем декодированное сообщение (слово a’), которое в идеале должно совпадать со словом a’.
Чтобы обеспечить надежные каналы связи необходимо решить две задачи:
1. Обнаружит ошибки в полученном сообщении по каналу связи;
2. Исправить полученное сообщение.
При математическом анализе канала связи пользуются упрощенными моделями канала связи. Простейшей моделью канала связи является двоичный симметричный канал связи.
В нем двоичные сигналы 0, 1 последовательно передаются по линии связи от передатчика на приемник. При этом считается, что каждый сигнал принимается правильно с вероятностью p и ошибочно с вероятностью q = 1 – p. Сверх того предполагается, что ошибки в передаче последовательных сигналов происходят независимо.
Применяя формулу Бернулли для последовательности независимых испытаний, получаем теорему.
Теорема 4. Вероятность, что при передаче по двоичному симметричному каналу связи (p, q) слова длины n в нем произойдет k ошибок, равна
Вероятность, что при передаче по двоичному симметричному каналу связи (p, q) слова длины n в нем произойдет не более k ошибок, равна
Пример 2. Пусть p = 0,999 . Тогда q = 0,001. Вероятность того, что при передаче слова длины 10 произойдет 0 ошибок равна (0,999)10 » 0,990; что произойдет 1 ошибка равна 10*(0,999)9(0,001) » 0,0099; что произойдет 2 ошибки равна 45*(0,999)8(0,001)2 » 0,00005. Этот пример показывает, что наиболее вероятно в канале связи произойдет одна ошибка (из тысячи слов в среднем 10 слов придут с одной ошибкой). Эти одиночные ошибки необходимо обязательно необходимо обнаружить и исправить при декодировании.
В этой лекции рассмотрены методы увеличения надежности передачи информации с использованием систематических кодов, большая часть которых принадлежит к групповым кодам, основанным на использовании теоремы Лагранжа. Идея, положенная в основу этого метода состоит в том, что передаваемые слова кодируются более длинными словами тех же символов 0, 1. Приемник способен распознавать и исправлять ошибки, пользуясь дополнительной информацией, содержащейся в добавочных символах.
Определение 1. Двоичным блочным (m,n)-кодом называется пара, состоящая из схемы кодирования (функции E: Bm® Bn) и схемы декодирования (функции D: Bn® Bm). Функции E и D выбираются таким образом, чтобы функция D° T°E, где T – функция ошибок, с вероятностью , близкой к единице, была тождественной. Таким образом математическую модель системы связи можно представить блок схемой (см. рис. 5).
Все коды делятся на два класса.
Коды с исправлением ошибок – имеют цель с вероятностью, близкой к единице, восстановить сообщение.
Коды с обнаружением ошибок – имеют цель с вероятностью, близкой к единице, выявить наличие ошибок.
Например, E(1001)=10010, E(1011)=10111.
При кодировании сумма цифр любого кодового слова четная, если сумма цифр, принятого по каналу слова, нечетная, то приемник указывает наличие ошибок в сообщении, если четная, то предполагается, что в сообщении ошибок не произошло. Схема декодирования
При кодировании с проверкой на четность будет обнаружена ошибка в полученном сообщении, если в нем произошло нечетное число ошибок в отдельных символах и не обнаружена ошибка в четном числе символов.
Вероятность не обнаружения ошибки в коде с проверкой на четность равна
Например, E(1001)= 100110011001, E(1011)= 101110111011.
Например, для (4,12) – кода D(101110010001) = 1001, D(001110110011)= 0011.
Вероятность того, что символ в данной позиции буде принят трижды правильно равна p3, вероятность одной ошибки 3 p3q. Таким образом, вероятность принятия правильно символа в одной позиции p3+3p3q, вероятность ошибочного приема символа в одной позиции q3+3q3p.
Например, при p = 0,1 один символ будет принят неправильно с вероятностью 0,027. Это снижает вероятность ошибки на один символ с 10% до 2,8%. Отметим, что тройное повторение обеспечивает исправление одной ошибки за счет тройного увеличения времени передачи. Существуют (3,6) – коды, которые также исправляют одну ошибку, но только удваивая время передачи.
Теорема 1. Для того чтобы код давал возможность обнаруживать все ошибки в не более чем k позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было равно k+1. Для такого кода вероятность того, что ошибка в сообщении не будет обнаружена, равна
Доказательство.Необходимость. Допустим, что код дает возможность обнаружить все ошибки в не более чем k позициях. Докажем, что наименьшее расстояние между кодовыми словами было равно k+1. Допустим противное, что есть кодовые слова, расстояние между которыми меньше k+1. Тогда можно сделать в каждом из этих слов не более k ошибок и перевести одно слова в другое слово. Тогда ошибку нельзя обнаружить, так как неизвестно из которого слова оно произошло. Получаем противоречие.
Достаточность. Пусть наименьшее расстояние между кодовыми словами было равно k+1. Тогда обнаруживаем неверное слово по правилу. Если оно не совпадает с кодовым словом, то в нем произошла ошибка. При этом, если в кодовом слове сделать не более k ошибок, то ошибка будет обнаружена..
Теорема 2. Для того чтобы код давал возможность исправить все ошибки в не более чем k позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было равно 2k+1.
Доказательство.Необходимость. Допустим, что код дает возможность исправить все ошибки в не более чем k позициях. Докажем, что наименьшее расстояние между кодовыми словами было равно2k+1. Допустим противное, что есть кодовые слова, расстояние между которыми меньше 2k+1. Тогда можно сделать в каждом из слов не k более ошибок и перевести оба слова в одно слово. Тогда ошибку нельзя исправить, так как неизвестно из которого слова оно произошло. Получаем противоречие.
Достаточность. Пусть наименьшее расстояние между кодовыми словами было равно2k+1. Тогда рассмотрим около каждого кодового слова шар радиуса k и декодируем все полученные сообщения по правилу: слово декодируем тем кодовым словом, которое находится от полученного слова на расстоянии не большем k, т.е. попадет в шар с центром в выбранном кодовом слове. При этом, если в кодовом слове сделать не более k ошибок, то оно будет восстановлено.
Для простого (1,3)-кода служит функция D; 000a0, 001a0, 010a0, 100a0, 011a0, 101a0, 110a0, 111a0, которая исправляет ошибки ровно в одной позиции.
С точки зрения групповой структуры удобно рассматривать строку ошибок. Работу канала связи можно объяснить следующим образом:
Примеры 1.(2,3)-код с проверкой четности E; 00a000, 01a011, 10a100, 11a110. Ни одна из строк ошибок 001, 010, 100, 111 не переводит кодовое слов в кодовое слово. Поэтому все однократные и тройные ошибки будут обнаружены.
2. (2,5)-код с проверкой четности E; 00a00000, 01a01011, 10a10101, 11a11110. Эта система кодирования способна исправлять любые однократные ошибки, так как ближайшее кодовое расстояние между словами равно .
Кодирование таблицами, задающими кодовое слово для каждого блока, требует большого объема памяти. Поэтому используется, так называемая методика матричная кодирования, при которой запоминаются только коды m слов, имеющие по одной единице.
Пусть Е = (eij)- матрица размерности m´n, состоящая из нулей и единиц. Если знак “+” обозначает сложение по модулю 2, то схема кодирования определяется уравнениями:
Последнее равенство можно записать матричным равенством:
b = aE. (3)
Преимущества матричного кодирования:
вместо 2m требуется заполнить только m слов;
в первых m символах кодового слова стоит слово сообщение;
при получении кодовых слов необходимо только сложить по 2 только те строки матрицы, номера которых совпадают с номерами тех символов кода сообщения, которые равны 1.
Примеры 3.(3,6)-код задаем следующей матрицей
Полный список кодовых слов
000a000000, 001a100110, 010a010011, 100a001111, 011a110101, 101a101001, 110a011100, 111a111010.
Определение 1. Блочный код называется групповым, если его кодовые слова образуют группу.
Теорема 1. Если код является групповым, то наименьшее расстояние между кодовыми словами равно наименьшему весу ненулевого кодового слова неравного нулю.
Доказательство.Пусть – кодовое слово наименьшего веса. Так как по теореме 4 параграфа 1 наименьшее расстояние d(a, b)между словамиd(a, b) = w(a – b) ³ w(m). Далее имеем w(m)= w(m – 0) = d(m, 0)³ d(a, b). Из полученных двух неравенств находим w(m) = d(a, b).
Следствие 1.Для того чтобы групповой код давал возможность обнаруживать все ошибки в не более чем k позициях, необходимо и достаточно, чтобы наименьший вес кодового слова был равен k+1.
Следствие 2.Для того чтобы групповой код давал возможность исправлять все ошибки в не более чем k позициях, необходимо и достаточно, чтобы наименьший вес кодового слова был равен 2k+1.
Теорема 2. Пусть Е – кодирующая m´n матрица, у которой есть единичная m´m подматрица. Тогда отображение aaaЕ является мономорфизмом группы Bm сообщений в группу Bn кодирующих слов.
Доказательство.Так как у кодирующей матрицы Е есть единичная подматрица, то кодовое слово, в которое кодируется слово a содержит всегда в качестве подслова слово a. Следовательно, указанное отображение переводит разные слова из Bm в различные кодовые слова из Bn, и является инъекцией. Так как для любых слов сообщений a, a’ имеем (a+ a’)Е = aЕ + a’Е, то указанное отображение является мономорфизмом.
По теореме 2 образ группы при указанном отображении изоморфен группе и поэтому является подгруппой группы . Таким образом доказана теорема.
Теорема 3. Пусть Е – кодирующая m´n матрица, у которой есть единичная m´m подматрица. Тогда отображение aaaЕ является групповым (m, n) – кодом.
Примеры 3.(3,6)-код рассмотренный в примере 3 предыдущего параграфа является групповым кодом, в котором наименьший вес кодового слова равен 3 и код способен исправлять однократные ошибки и обнаруживать двойные.
Групповые коды не обнаруживают только такие ошибки, которые сами являются кодовыми словами, так как только при таких ошибках одни кодовые слова перейдут в другие кодовые слова. Вероятность, что ошибка не будет обнаружена равна сумме вероятностей всех строк ошибок, т.е. кодовых слов.
В примере 1 она равна 4p3q3 + 3p2q4.
Схема декодирования группового кода. Разложим группу Bn на классы смежности по подгруппе K кодовых слов:
Теорема 4. В любом групповом коде, любой элемент xÎBn однозначно представляется в виде суммы x = bj + hk кодового словаbj и лидера hi..
Матрица декодирования содержит все элементы из Bn и имеет вид
Пример 1.Рассмотрим (3,6) – код из примера 3 п.2 с матрицей кодирования
где совокупность кодовых слов 000a000000, 001a100110, 010a010011, 100a001111, 011a110101, 101a101001, 110a011100, 111a111010.
Чтобы декодирование принятое слово x = bj + hk следует отыскать его в таблице декодирования и выбрать в качестве передаваемого слова кодового слова bj в том же столбце, но в первой строке. Затем слово bj декодировать.
Например, если принято слово 010010, то считается что передано слово 010011 и при передач произошла ошибка в шестом символе. Далее слово дешифруется словом 010.
Теорема 5. Групповое кодирование посредством лидеров справляет в точности те строки ошибок, которые являются лидерами.
Вероятность правильного декодирования, переданного по двоичному симметричному каналу слова равна сумме вероятностей всех лидеров, включая нулевой. В нашем примере для слова длины 6 вероятность правильного декодирования равна p6 + 6p5q + p4q2.
Теорема 6. Если все лидеры является словами наименьшего веса в своем классе, то кодовое слово, стоящее в данном столбце, является ближайшим кодовым словом ко всем словам этого столбца.
Доказательство.Пусть мы передали слово bj и приняли слово bj + ej. Расстояние от bj до bj +ej равно w(ej). Расстояние от до любого другого кодового слова равно весу разности этих слов, которая лежит в том же смежном классе, что и bj. Поэтому этот вес не меньше веса лидера.
Последняя теорема означает, что такой выбор оптимален, так как минимизирует вероятность ошибки при передаче по двоичному симметричному каналу.
Групповой код не обнаруживает и не исправляет в точности те ошибки, которые совпадают с кодовыми словами. Поэтому вероятность не обнаружения ошибки при групповом кодировании равна вероятности появления ошибок равных кодовым ненулевым словам. В нашем примере вероятность равна 4p3q3 + 3p2q4 .
Геометрическая интерпретация. Кодирующая схема двоичного (m,n)- кода определяет инъекцию множества Bm сигналов длины m в гиперкуб Bn. В графе, вершины которого являются вершинами гиперкуба, а ребра его ребрами, расстояние между вершинами совпадает с расстоянием между соответствующими словами.
Схема декодирования отображает Bn в Bm, так что прообраз каждого слова длины m состоит в точности из тех словиз Bn, которые будут декодированы данным словом. Чтобы кодирование исправило все ошибки веса £ w, каждый такой класс эквивалентности должен содержать шар радиуса w с центром E(a), состоящий из слов, расстояние которых от кодового слова не больше w. Таких слов имеется
Код называется совершенным, если все классы эквивалентности являются такими шарами
Чтобы блочный (m,n) – код был совершенным, необходимо выполнение условия
Опишем процедуру построения (m, m+r) кода Хемминга.
1) Выберем целое положительное число r из условия 2r-1-1< m+r £ 2r-1, 2r-1-1- r < m £ 2r-1- r. Можно всегда считать m = 2r-1-1- r, n = 2r-1-1. Сообщениями будут слова длины m, а кодовые слова длины m+r.
Например, при (m, m+4) -кода Хемминга имеем 24-1-1- 4 < m £ 24-1-4, 3 < m £ 11.
Например, для (10,14) кода Хемминга при символы
– контрольные, а
– символы сообщения.
3) Построим матрицу M из m+r строк и r столбцов. В i-й строке матрицы M стоят символы двоичного разложения числа i.
Например, для (1,3)-кода, (4,7)-кода, (9,13)-кода, (11,15)-кода Хемминга эти матрицы имеют соответственно вид:
4) Запишем систему уравнений bM=0 , где M – матрица, указанная выше. Она состоит из r уравнений. Контрольный символ
находятся сложением по модулю 2 тех символов bk кодируемого слова, для которых в i- столбце и k-й строке и матрицы М стоит единица.
Например, для (4,7)-кода система уравнений имеет вид:
Декодирование. Пусть принято слово x = b+ e, где b – переданное слово, e – строка ошибок. Так как bM=0, то (b+ e)M = bM + eM = 0 + eM = eM. Если результат нулевой, как происходит при правильном приеме, то считается, что ошибок нет. Если вектор ошибок имеет единицу в i-й позиции,
, то при умножении e на M получается i-я строка матрицы, т. е. двоичное разложение числа i. Тогда следует изменить в принятом слове символ в i -й позиции слова .
Пример 1. Рассмотрим (4, 7) – код Хемминга. Матрица М=М7,3 которого имеет вид
Возьмем слово сообщение a = 0111. Решая указанную выше систему находим слово сообщение b = 0001111.
Имеем bM=0. Добавим к b строку ошибок e = 0000100. Тогда b+ e = 0001011 и (b+ e) М =101. Это двоичное представление числа 5, так что ошибка находится в 5-й позиции. Если e = 0000001, то (b+ e) М =111, т.е. 7 в двоичной записи, поэтому в 7-й позиции ошибка.
Если ошибка допущена более чем водной позиции, декодирование даст неверный результат. Например, если строка ошибок e будет кодовой, то (b+ e) М =0, и декодирование не изменит принятого слова. Если ошибка допущена в двух позициях, код укажет позицию, но неправильно. Например, если e = 0000101, то (b+ e) М =010, т.е. 2 в двоичной записи, поэтому во 2-й позиции ошибка. Последнее неверно.
Если к этому коду добавить проверку четности, то получим код наименьшего веса 4, способный устранять ошибку в одной позиции и обнаруживать ошибки в двух позициях.
Отметим, что коды Хемминга совершенные, минимальное кодовое расстояние в коде Хемминга равно 3 и они исправляют все одинарные ошибки и ни каких других ошибок они не исправляют. В таблице декодирования у такого кода будет 0 и все m строки ошибок ровно с одной единицей. В обще случае совершенный код исправляющий все ошибки в не более чем k позициях должен иметь лидерами все строки веса не более чем k, т.е. с не более чем k единицами.
Линейными называются такие двоичные коды, в которых множество всех разрешенных блоков является линейным пространством относительно операции поразрядного сложения по модулю 2. Очевидно, что оно является подпространством линейного пространства, образуемого множеством всех (а не только разрешенных) двоичных последовательностей длины п. Чтобы разрешенные блоки были линейным пространством, они должны содержать нулевой элемент, т. е. блок, состоящий из п нулей, должен быть разрешенным, а сумма (поразрядная по модулю 2) любых разрешенных блоков должна быть также разрешенным блоком. Линейные коды называют также групповыми. Двоичный линейный ,код можно построить следующим образом. Среди всех 2n последовательностей кодовых символов можно выбрать различными способами п линейно-независимых. В частности, ими могут быть (но не обязательно) элементы, образующие ортогональный базис. Выберем из них k любых линейно-независимых блоков, которые обозначим
и образуем все линейные комбинации вида
В общем случае производящая матрица двоичного кода записывается в виде
Здесь bij — двоичный символ (0 или 1), находящийся на j-м разряде i-гo кодового слова (входящего в выбранный базис).
Полученный таким образом код, содержащий 2k блоков длиной я, обозначают (n, k). При заданных п и k существует много различных (п, k) -кодов с различными кодовыми расстояниями d, определяемых различными порождающими матрицами. Все они имеют избыточность
или относительную скорость Vk = k/n.
Заметим, что если две порождающие матрицы различаются только порядком расположения столбцов, то определяемые ими коды являются изоморфными пространствами. Такие коды называют эквивалентными. Они имеют одинаковые кодовые расстояния между соответственными парами кодовых векторов и, следовательно, одинаковые способности обнаруживать и исправлять ошибки.
Чаще всего применяют систематические линейные коды, которые строят следующим образом. Сначала строится простой код длиной k, т. е. множество всех k-последовательностей двоичных символов, называемых информационными. Затем к каждой из этих последовательностей приписывается r=n—k проверочных символов, которые получаются в результате некоторых линейных операций над информационными символами. Можно показать, что для каждого линейного кода существует эквивалентный ему систематический код.
Простейший систематический код (п, п—1) строится добавлением к комбинации из п-1 информационных символов одного проверочного, равного сумме всех информационных символов по модулю 2. Легко видеть, что эта сумма равна нулю, если среди информационных символов содержится четное число единиц, и равна единице, если число единиц среди информационных символов нечетное. После добавления проверочного символа образуются кодовые комбинации, содержащие только четное количество единиц, т. е. комбинации с четным весом.
Такой код (n, п-1) имеет d=2, поскольку две различные кодовые комбинации, содержащие по четному числу единиц, не могут различаться в одном разряде. Следовательно, он позволяет обнаружить одиночные ошибки. Легко убедиться, что, применяя этот код в схеме декодирования с обнаружением ошибок, можно обнаруживать все ошибки нечетной кратности. Для этого достаточно подсчитать число единиц в принятой комбинации и проверить, является ли оно четным. Если при передаче комбинации произойдут ошибки в нечетном числе разрядов q, то принятая комбинация будет иметь нечетный вес и, следовательно, окажется запрещенной. Такой код называют кодом с одной проверкой на четность.
где γij коэффициенты (0 или 1), характеризующие данный код. Если набор все коэффициентов γij собрать в таблицу (матрицу), и получим так называемую проверочную матрицу кода H размерности
Единицы в каждой j-той строке матрицы H показывают, какие информационные символы нужно сложить по модулю 2, чтобы получить нуль.
Из (1.46) можно придти к выводу, что произведение порождающей и транспонированной проверочной матриц
Для рассмотренного примера кода (п, n—1) с четным весом проверочная матрица вырождается в вектор-строку длиной п:
а порождающая матрица имеет вид
Рассмотрим другой пример систематического кода — код, заданный порождающей матрицей
или проверочной матрицей
Этот код имеет d=3 и позволяет обнаруживать все одиночные и двойные ошибки или исправлять (по алгоритму Хэмминга) все одиночные ошибки.
Заметим, что строки проверочной матрицы являются линейно независимыми векторами. Следовательно, проверочная матрица может служить порождающей для другого линейного кода (п, n—k), называемого двойственным. Так, например, матрица (1.51) является порождающей матрицей кода, имеющего d=4. Матрица (1.50) является проверочной для этого кода.
Преимуществом линейных, в частности систематических, кодов является то, что в кодере и декодере не нужно хранить список из 2k блоков, а при декодировании не нужно вычислять 2k расстояний. Вместо этого достаточно хранить, например, n—k строк проверочной матрицы и при декодировании проверять выполнение n—k равенств. Так, например, при коде (100, 50) нужно хранить 50 строк по 100 символов, т. е. всего 5000 символов, а не 1017, как при табличном кодировании, и проверять 50 равенств, вместо перебора 1015 расстояний.
Таким образом, код позволяет исправить все одиночные ошибки.
Из этого примера видно, что при декодировании систематического кода не требуется перебирать таблицу, содержащую 2k кодовых комбинаций, и производить п—k сравнений. Помимо тех операций, которые осуществляются в кодере, декодер должен произвести п—k сравнений и перебрать таблицу исправлений, содержащую 2n-k строк. Для такого кода, как, это осуществляется просто, но зато код оказывается малоэффективным.
Как неоднократно отмечалось, для получения высокой верности связи следует применять коды с достаточно большой длиной. Однако с ростом п, если отношение k/n (скорость кода) фиксировано, растет и разность п—k, а следовательно, и объем таблицы исправлений, равный 2n-k. Так, для кода он равен 218 = 262 144.
Следовательно, применение систематического кода в общем случае хотя и позволяет упростить декодирование по сравнению с табличным методом, все же при значениях п порядка нескольких десятков не решает задачи практической реализации.
Если (п, k) -код используется для обнаружения ошибок, то в теории кодирования доказывается, что при любой вероятности ошибочного приема символа р≤1/2 найдется код, для которого
Более того, при любых п и k существует код, который в любом двоичном симметричном канале без памяти обеспечивает выполнение неравенства (5.25), какова бы ни была вероятность ошибки
Такие коды называются равномерно обнаруживающими ошибки.
Таким образом, увеличивая число корректирующих символов, можно обеспечить сколь угодно (малую вероятность необнаруженной ошибки (и, следовательно, вероятность выдачи получателю ложной информации). Однако при сохранении скорости кода k/n это потребует увеличения длины блока п. При большой длине блока вероятность появления обнаруживаемой ошибки возрастает и, следовательно, увеличиваются трудности восполнения потерянной информации.
К наиболее простым двоичным систематическим кодам относят коды Хэмминга с d=3. Для любого натурального числа rсуществует код Хэмминга при п=2r—1 и k = n—r. Двойственными кодами к кодам Хэмминга являются эквидистантные коды при n=2r—1, k = r и d = 2r-1 ,причем расстояние между любой парой кодовых комбинаций одинаково, чем и обусловлено название кодов. Коды Хэмминга и эквидистантные обладают свойством равномерно обнаруживать ошибки.
Теория помехоустойчивости кодирования достигла больших успехов. Предложен ряд кодов и способов декодирования, при которых сложность декодера растет не экспоненциально, а лишь как (некоторая степень n ).
Например, вес Хемминга вектора U = ( 1001011 ) равен четырем, для вектора U = ( 1111111 ) величина w(U)составит 7 и т.д.
Таким образом, чем больше единиц в двоичной последовательности, тем больше ее вес Хемминга.
Далее, пусть U и V будут двоичными последовательностями длиной n.
Пример. Определим расстояние Хемминга между словами
Для конечного множества
можно определить Относительное расстояние Хэмминга:
Пример 35. На универсальном множестве
Применяя формулу расстояния Хэмминга между множествами, получим: , а для относительного расстояния Хэмминга имеем:
Коды Хемминга – это
– РєРѕРґС‹, РіРґРµ
, позволяющие исправлять однократную ошибку. На примере кодов Хемминга мы изучим матричное кодирование.
Проверочная матрица кода Хемминга
Матрица М называется проверочной матрицей
Пример. Покажем, что матрица
является проверочной матрицей кода Хемминга.
Порождающая матрица кода Хемминга
По проверочной матрице кода Хемминга
строится порождающая матрица кода Хемминга
– единичная матрица РїРѕСЂСЏРґРєР°
Пример. Определим порождающую матрицу кода Хемминга
Решение. Единичная матрица порядка
, а матрица
при транспонировании превратится в матрицу
, поэтому порождающая матрица кода Хемминга равна
Пример. Кодируем сообщение
Решение. Кодированное сообщение равно
Коды Хемминга позволяют исправлять однократную ошибку. Предположим, что получено кодированное сообщение
. Если при умножении проверочной матрицы М на вектор
получается нулевой вектор
Если результатом умножения проверочной матрицы М на вектор
надо изменить символ в той позиции, номер которой равен номеру столбца проверочной матрицы М, совпадающего с вектором
Пример. Декодируем сообщение
Решение. Умножим проверочную матрицу
Полученный вектор совпадает с 1-м столбцом проверочной матрицы М. поэтому надо изменить 1-й символ сообщения
. Получим вектор (1110010). Первые
=4 символа (1110) и составляют декодированное сообщение.
Алгоритм построения кода Хаффмана.
1. Расположить знаки в порядке убывания частот.
2. Объединить два знака с наименьшими частотами в один составной знак.
Пример 1. В таблице указаны частоты букв. Построим по этим данным код Хаффмана.
Объединим РґРІРµ Р±СѓРєРІС‹ СЃ наименьшими частотами (РЅ, m) РІ РѕРґРёРЅ составной знак (РЅm). Ртому знаку припишем частоту, равную СЃСѓРјРјРµ частот Р±СѓРєРІ
н, m (9+8=17). После этого расположим все знаки в порядке убывания частот.
Объединим РґРІРµ Р±СѓРєРІС‹ СЃ наименьшими частотами (Р°, Рё) РІ РѕРґРёРЅ составной знак (аи). Ртому знаку припишем частоту, равную СЃСѓРјРјРµ частот Р±СѓРєРІ
а, и (15+15=30). После этого расположим все знаки в порядке убывания частот
На 3-м шаге будет получена следующая таблица.
На 4-м шаге будет получена следующая таблица.
На последнем шаге получаем (аи(о))(е(нm)).
0 (аи)о
0 1 Рѕ
1 (Рµ)РЅm 1 0
0 1 Рё
1 0 РЅ
Получаем таблицу кодирования.
Пример 2. Кодируем слово «енот» по таблице примера 1.
Решение. Так как по таблице кодирования е=10, н=110, о=01, m=111, то слово «енот» кодируется последовательностью 1011001111.
Пример 3. Декодируем по дереву сообщение 1100101111.
Оставшаяся часть сообщения – это 01111. Символы 01 дают букву о. а символам 111 соответствует буква m.
Декодированное сообщение нооm.
Код Хаффмана широко используется в кодировании изображений.
код определяется двумя функциями К:
Коды делятся на коды с обнаружением ошибок и коды с исправлением ошибок.
– матрица РїРѕСЂСЏРґРєР°
, элементами которой являются 0 и 1, соответствующая
коду, называемая порождающей матрицей кода ;
Н-р, порождающей матрице
кода с повторениями будет матрица
, так как
Запишем матричное уравнение:
. Здесь матрицы М порядка
для кода Хемминга (при
Если принято слово
, где е –ошибка, то
, то считают, что ошибки нет. Если е имеет 1 в i-й позиции, то в слове с нужно изменить символ b в i-й позиции, и полученное слово будет результатом декодирования. Если единицы есть больше, чем в одной позиции, то результат декодирования неверен.
mybiblioteka.su – 2015-2023 РіРѕРґ. (0.077 сек.)