владимиров математические основы теории помехоустойчивого кодирования
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ
1 ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. проф. М. А. БОНЧ-БРУЕВИЧА» С. С. Владимиров МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ Курс лекций Санкт-Петербург 2014
2 5. Линейные блочные коды и коды Хэмминга Линейные блочные коды позволяют представить информационные и кодовые слова в виде двоичных векторов, что позволяет описать процессы кодирования и декодирования с помощью аппарата линейной алгебры, с учетом того, что компонентами вводимых векторов и матриц являются символы «0» и «1». Операции над двоичными компонентами производятся при этом по правилам арифметики по модулю 2 [?]. Множество 2 k возможных двоичных информационных слов блокового (n,k)-кода взаимно однозначно отображается в множество 2 k кодовых слов длиной n. Далее рассмотрим механизм исправления и обнаружения ошибок в помехоустойчивом кодировании. Для этого удобно рассмотреть множество двоичных слов (векторов) длиной n в виде точек на плоскости (см. рис. 5.1). Ранее были рассмотрены такие важные параметры, как кодовое расстояние d и минимальное кодовое расстояние d min, а также связанный с минимальным кодовым расстоянием параметр гарантированно исправляемой кратности ошибки t. На рис. 5.1 черными кругами показаны два кодовых слова c 1 и c 2, отличающиеся друг от друга в d min двоичных символов. Вокруг них показаны области, содержащие слова длиной n, отличающиеся от этих кодовых слов не более чем в t позициях. Прочие кодовые слова показаны черными ромбами. c 1 c 2 t d min Рис Общий принцип исправления и обнаружения ошибок В случае, если по каналу было передано кодовое слово c 1, и оно пришло с искажениями, возможны три варианта декодирования с исправлением ошибки. 1. Было получено слово, попадающее в область вокруг вектора c 1. Такое слово будет преобразовано декодером в слово c 1 и декодирование будет осуществлено верно. 2. Если получено слово, не принадлежащее областям ни одного кодового слова, то оно не может быть декодировано и, следовательно, возникает ошибка декодирования. 3. Слово, попадающее в область вокруг c 2, будет преобразовано декодером в c 2. Такая ошибка не может быть обнаружена. 39
3 В показанном на рис. 5.1 случае не все слова размерности n принадлежат областям декодирования. Таких кодов большинство. Коды, в которых непересекающиеся области декодирования охватывают все пространство слов размерности n, называются совершенными или плотноупакованными. При использовании совершенных кодов всегда возможна коррекция ошибок (не всегда правильная). Декодер такого кода не может определить ошибку декодирования. Он работает либо в режиме определения ошибок, либо в режиме исправления ошибок. Основными совершенными кодами являются коды Хэмминга и коды Голея [?]. Код Хэмминга можно построить для любого натурального числа r 3. Этот код будет обладать рядом свойств [?]. n = 2 r 1 k = 2 r 1 r r = n k d min = 3, t = 1 Далее будем рассматривать процессы кодирования и декодирования линейных блочных кодов на примере кодов Хэмминга Кодирование линейных блочных кодов Поскольку между информационными и кодовыми словами существует взаимно однозначное соответствие, процесс кодирования может быть осуществлен с использованием таблицы соответствий, хранящейся в памяти кодера. Однако, для длинных кодов такой метод неприемлем, так как требует большой объем памяти для хранения таблицы. Вместо этого вводится понятие так называемой порождающей матрицы G. Оно основано на том, что подпространство всех кодовых слов линейного блочного (n,k)-кода имеет некоторый базис (v 0,v 1. v k 1 ), через который может быть выражено любое кодовое слово этого кода [?]. v = u 0 v 0 + u 1 v u k 1 v k 1, (34) где u i <0,1>, 0 i 4 где u = (u 0,u 1. u k 1 ) информационное слово [?]. Фактически, формула (36) описывает процедуру кодирования линейного блочного кода посредством образующей матрицы. Для пространства кодовых слов линейного (n, k)-кода существует дуальное ему пространство кода (n, n k), порождаемое матрицей H размера (n k) n. Такая матрица получила название проверочной для кода (n,k) и обладает следующими свойствами GH T = 0, vh T = 0, (37) на основе которых реализована операция декодирования линейных блочных кодов [?]. Как правило рассматривают так называемые систематические или каноничные формы матриц G и H, использующиеся для процедуры систематического кодирования. На практике, любая порождающая матрица G линейного блочного (n, k)-кода может быть преобразована к систематическому виду посредством элементарных операций и перестановок столбцов матрицы [. ]. Матрица G в систематической форме состоит из двух подматриц: единичной матрицы I k размера k k и проверочной подматрицы P размера k (n k) [?]. G k n = (P k (n k) I k ). (38) Соответственно, исходя из свойства (37), следует, что проверочная матрица H состоит из единичной матрицы I n k и транспонированной проверочной подматрицы P [?]. H (n k) n = (I n k Pk (n k) T ). (39) В качестве примера приведем порождающую (40) и проверочную (41) матрицы для кода Хэмминга (7,4) G (7,4) = (40) H (7,4) = (41) Для примера также рассмотрим процедуру кодирования с использованием порождающей матрицы G (40). В качестве информационного слова возь- 41
5 мем вектор u = [ ] v = u G (7,4) = [ ] = [ ]. (42) 5.2. Декодирование линейных блочных кодов Как и в случае кодирования, декодирование линейных блочных кодов можно осуществлять посредством таблицы по принципу максимального правдоподобия. В этом случае производится последовательное поразрядное сравнение принятого на вход декодера слова со всеми возможными кодовыми словами. В результате будет выбрано кодовое слово, имеющее наименьшее число отличий от декодируемого. В случае несовершенных кодов возможен вариант, когда есть несколько кодовых слов, отличающихся от принятого в одинаковом числе разрядов. Соответственно, декодер не может принять решение о верности одного из вариантов и выдает сигнал о невозможности декодирования. Недостатки такой схемы те же, что и в случае кодирования необходим большой объем памяти для хранения всех кодовых слов в случае длинных кодов. Быстродействие для длинных кодов также значительно увеличивается. В связи с этим используют механизм синдромного декодирования, основанный на использовании проверочной матрицы H. Для понимания принципа декодирования рассмотрим как выражаются проверочные символы кодового слова через информационные на примере систематического кода Хэмминга (7,4). v 0 = v 3 v 5 v 6 ; v 1 = v 3 v 4 v 5 ; v 2 = v 4 v 5 v 6. Если в канале произошла ошибка, то для принятого вектора r хотя бы одно из равенств выполняться не будет. Эти проверочные соотношения можно записать для принятого вектора в виде системы уравнений (43). r 0 r 3 r 5 r 6 = s 0 ; r 1 r 3 r 4 r 5 = s 1 ; r 2 r 4 r 5 r 6 = s 2. (43) Соответственно, если хотя бы один из компонент вектора s = не равен нулю, то в принятом слове есть ошибка [?]. 42
6 Уравнения (43) можно записать через проверочную матрицу H. s = r H T. (44) Вектор s принято называть синдромом. Таким образом, ошибка в принятом слове будет обнаружена, если хоть один компонент синдрома принятого слова не равен нулю [?]. Для исправления ошибки используется тот факт, что каждый синдром соответствует своей позиции одиночной ошибки (мы говорим о кодах Хэмминга). Таким образом, перебрав все возможные варианты одиночной ошибки можно получить таблицу соответствия синдром-ошибка. В табл. 5.1 приведены соответствия позиций ошибки и синдромов для кода Хэмминга (7,4) [?]. Таблица 5.1 Таблица соответствия синдром-ошибка для кода Хэмминга (7,4) Позиция ошибки r 0 r 1 r 2 r 3 r 4 r 5 r 6 Синдром [1 0 0] [0 1 0] [0 0 1] [1 1 0] [0 1 1] [1 1 1] [1 0 1] Если сравнить табл. 5.1 и проверочную матрицу (41), то можно увидеть, что ошибке в i-й позиции кодового слова соответствует синдром, образованный i-м столбцом матрицы H [?]. Для примера рассмотрим декодирование полученной ранее кодовой комбинации v = [ ] без ошибок и с ошибкой в позиции v 4. При отсутствии ошибки синдром будет равен s = v H T = [ ] = [0 0 0], что доказывает отсутствие ошибки Если наложить на вектор v ошибку в позиции v 4 будет получен вектор r = [ ]. Теперь синдром будет равен s = r H T = [ ] = [0 1 1],
7 что, во-первых, показывает наличие ошибки, а во-вторых, согласно табл. 5.1, указывает, что она произошла в позиции r 4. Таким образом, ошибка может быть исправлена Расширенные коды Хэмминга Расширение кода Хэмминга заключается в дополнении кодового слова дополнительным двоичным разрядом так, чтобы оно содержало четное число единиц. Такое расширение дает ряд преимуществ [?]. 1. Длина кода увеличивается до n = 2 r, что удобнее для хранения и передачи информации. 2. Минимальное расстояние d min = 4, следовательно t обн = 3. Также, дополнительный разряд позволяет использовать декодер в гибридном режиме обнаружения и коррекции ошибок. Для примера рассмотрим расширение кода Хэмминга (7, 4) расширенный код Хэмминга (8,4). Кодовый вектор ṽ = (ṽ 0,ṽ 1. ṽ 7 ) расширенного кода (8,4) получается из вектора v = (v 0,v 1. v 6 ) кода (7,4) путем добавления разряда проверки на четность, то есть где ṽ = (ṽ 0,ṽ 1. ṽ 7 ) = (ṽ 0,v 0,v 1. v 6 ), ṽ 0 = 6 i=0 Проверочная матрица кода (8, 4) получается из проверочной матрицы кода (7,4) в два приема [?]. 1. Слева к матрице H (7,4) дописывается нулевой столбец. 2. Полученная матрица дополняется сверху строкой из единиц. v i H (8,4) = (45) При синдромном декодировании s = ṽ H T (8,4) (46) 44
8 вектор синдрома имеет вид s = ( s 0,s 0,s 1,s 2 ) = ( s 0,s), (47) где компонента s 0 равна сумме всех элементов кодового слова ṽ и, следовательно, равна нулю. Далее рассмотрим процесс коррекции и обнаружения ошибок. Процедура исправления одиночных ошибок совпадает с таковой для обычных кодов Хэмминга. Компонента s 0 при этом всегда равна единице, а синдром s соответствует синдрому обычного кода Хэмминга. Если же ошибка в дополнительном разряде ṽ 0, то s 0 будет равно 1, а s = (000). При двукратной же ошибке компонента s 0 всегда будет равна нулю. Таким образом можно представить гибридный алгоритм коррекции ошибок. 1. Если s 0 = 1, то исправление одиночной ошибки. 2. Если s 0 = 0 и s 0, то обнаружена неисправляемая ошибка. 45
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им.
Электронные средства сбора, обработки и отображения информации
Оглавление
Помехоустойчивое кодирование
Понятие корректирующего кода
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала.
Построение такого кода достигается ценой введения избыточности. То есть, применяя для передачи информации код, у которого используются не все возможные комбинации, а только некоторые из них, можно повысить помехоустойчивость приема. Такие коды называют избыточными или корректирующими. Корректирующие свойства избыточных кодов зависят от правил построения этих кодов и параметров кода (длительности символов, числа разрядов, избыточности и др.).
В настоящее время наибольшее внимание уделяется двоичным равномерным корректирующим кодам. Они обладают хорошими корректирующими свойствами и их реализация сравнительно проста.
Наиболее часто применяются блоковые коды. При использовании блоковых кодов цифровая информация передается в виде отдельных кодовых комбинаций (блоков) равной длины. Кодирование и декодирование каждого блока осуществляется независимо друг от друга, то есть каждой букве сообщения соответствует блок из п символов.
Блоковый код называется равномерным, если п (значность) остается одинаковой для всех букв сообщения.
Различают разделимые и неразделимые блоковые коды.
При кодировании разделимыми кодами кодовые операции состоят из двух разделяющихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода занимают одни и те же позиции.
При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.
Непрерывными называются такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. Непрерывные коды также могут быть разделимыми и неразделимыми.
Общие принципы использования избыточности
Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На ввод кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из п двоичных символов, причем n>k. Всего может быть 
различных входных последовательностей и 
различных выходных последовательностей. Из общего числа 
выходных последовательностей только 
последовательностей соответствуют входным. Будем называть их разрешенными кодовыми комбинациями. Остальные ( 
— 
) возможных выходных последовательностей для передачи не используются. Их будем называть запрещенными кодовыми комбинациями.
— 
случаев безошибочной передачи;
— 
·(
-1) случаев перевода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;
— 
·( 
— 
) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.
Часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи соответствует:
Кобн 
.
Рассмотрим, например, обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (п=k+1). Общее число выходных последовательностей составит 
, то есть вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество 
комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого четного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть обнаруженных ошибок составляет:
Кобн 
.
Пример кодирующего устройства с проверкой на четность показан на рис.
Основные параметры корректирующих кодов
Основными параметрами, характеризующими корректирующие свойства кодов являются избыточность кода, кодовое расстояние, число обнаруживаемых или исправленных ошибок.
Рассмотрим суть этих параметров.
Избыточность корректирующего кода может быть абсолютной и относительной. Под абсолютной избыточностью понимают число вводимых дополнительных разрядов
Относительной избыточностью корректирующего кода называют величину
отн 
отн.
Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. Ее еще называют относительной скоростью передачи информации.
Если производительность источника равна Н символов в секунду, то скорость передачи после кодирования этой информации будет равна
поскольку в последовательности из п символов только k информационных.
Если число ошибок, которое нужно обнаружить или исправить, значительно, необходимо иметь код с большим числом проверочных символов. Скорость передачи информации при этом будет уменьшена, так как появляется временная задержка информации. Она тем больше, чем сложнее кодирование.
Кодовое расстояние характеризует cтепень различия любых двух кодовых комбинаций. Оно выражается числом символов, которыми комбинации отличаются одна от другой.
Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.
Кодовое расстояние может быть различным. Так, в первичном натуральном безызбыточном коде это расстояние для различных комбинаций может различаться от единицы до п, равной значности кода.
Число обнаруживаемых ошибок определяется минимальным расстоянием 
между кодовыми комбинациями. Это расстояние называется хэмминговым.
В безызбыточном коде все комбинации являются разрешенными, 
=1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.
Теорема. Чтобы код обладал свойствами обнаруживать одиночные ошибки, необходимо ввести избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух.
Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как 
=1. Если 
=2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.
Пусть подмножество разрешенных комбинаций образовано по принципу четности числа единиц. Тогда подмножества разрешенных и запрещенных комбинаций будут такие:
Очевидно, что искажение помехой одного разряда (одиночная ошибка) приводит к переходу комбинации в подмножество запрещенных комбинаций. То есть этот код обнаруживает все одиночные ошибки.
В общем случае при необходимости обнаруживать ошибки кратности 
— минимальное хэммингово расстояние должно быть, по крайней мере, на единицу больше 
, то есть
+1.
В этом случае никакая ошибка кратности 
не в состоянии перевести одну разрешенную комбинацию в другую.
Ошибки можно не только обнаруживать, но и исправлять.
Теорема. Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние должно быть не менее трех.
Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.
Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:
В общем случае исправляемые ошибки кратности 
связаны с кодовым расстоянием соотношением
=2
+1. (2.1)
где 
— сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).
Если, например, п=7, 
=1, то из (2.1)
Нужно отметить, что каждый конкретный корректирующий код не гарантирует исправления любой комбинации ошибок. Коды предназначены для исправления комбинаций ошибок, наиболее вероятных для заданного канала связи.
Групповой код с проверкой на четность
Недостатком кода с четным числом единиц является необнаружение четных групповых ошибок. Этого недостатка лишены коды с проверкой на четность, где комбинации разбиваются на части, из них формируется матрица, состоящая из некоторого числа строк и столбцов:
Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы 
. Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце:
.
При таком кодировании четные групповые ошибки обнаруживаются. Не обнаруживаются лишь такие ошибки, при которых искажено четное число символов в столбце.
Можно повысить обнаруживающую способность кода путем одновременной проверки на четность по столбцам и строкам или столбцам и диагоналям (поперечная и диагональная проверка).
Если проверка проводится по строкам и столбцам, то код называется матричным.
Проверочные символы располагаются следующим образом:
;
.
В этом случае не обнаруживаются только ошибки четной кратности с кратностью 4, 8, 16 и т.д., при которых происходит искажение символов с попарно одинаковыми индексами строк столбцов. Наименьшая избыточность кода получается в том случае, когда образуемая матрица является квадратной.
Недостатком такого кода является необходимость внесения задержки в передачу информации на время, необходимое для формирования матрицы.
Матричный код позволяет исправлять одиночные ошибки. Ошибочный элемент находится на пересечении строки и столбца, в которых имеется нарушение четности.
Коды с постоянным весом
Весом называется число единиц, содержащихся в кодовых комбинациях.
В коде «3 из 7» возможных комбинаций сто двадцать восемь (
=128), а разрешенных кода только тридцать пять. Относительная избыточность отн = 0,28.
Схема устройства определения веса комбинаций кода «3 из 7» приведена на рис. 2.6.
Циклические коды
Циклические коды характеризуются тем, что при циклической перестановке всех символов кодовой комбинации данного кода образуется другая кодовая комбинация этого же кода.
— комбинация циклического кода;
— также комбинация циклического кода.
Например, комбинация 1001111 (п=7) будет представлена многочленом
При таком представлении действия над кодовыми комбинациями сводятся к действиям над многочленами. Эти действия производятся в соответствии с обычной алгебры, за исключением того, что приведение подобных членов осуществляется по модулю 2.
Обнаружение ошибок при помощи циклического кода обеспечивается тем, что в качестве разрешенных комбинаций выбираются такие, которые делятся без остатка на некоторый заранее выбранный полином G(x). Если принятая комбинация содержит искаженные символы, то деление на полином G(x) осуществляется с остатком. При этом формируется сигнал, свидетельствующий об ошибке. Полином G(x) называется образующим.
Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:
Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже п.
Часто в качестве полинома, на который осуществляется деление, берется полином G(x)=
+1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.
Большим преимуществом циклических кодов является простота построения кодирующих и декодирующих устройств, которые по своей структуре представляют регистры сдвига с обратными связями.
Число разрядов регистра выбирается равным степени образующего полинома.
Обратная связь осуществляется с выхода регистра на некоторые разряды через сумматоры, число которых выбирается на единицу меньше количества ненулевых членов образующего полинома. Сумматоры устанавливаются на входах тех разрядов регистра, которым соответствуют ненулевые члены образующего полинома.
На рис. 2.7 приведена схема кодирующего регистра для преобразования четырехразрядной комбинации в семиразрядную.
В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.
Свойства циклического кода:
1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;
2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;