Глава 3. Количественная оценка информации 10 страница

Таблица 6.5

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

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

Рассмотрим в качестве примера опознаватели для кодов предназначенных исправлять единичные ошибки (табл. 6.6).

Таблица 6.6

В принципе можно построить код, усекая эту таблицу на любом уровне. Однако из таблицы видно, что оптимальными будут коды (7, 4), (15, 11), где первое число равно n, а второе k, и другие, которые среди кодов, имеющих одно и то же число проверочных символов, допускают наибольшее число информационных символов.

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

Предположим, что в результате первой проверки на четность для младшего разряда опознавателя будет получена единица. Очевидно, это может быть следствием ошибки в одном из разрядов, опознаватели которых в младшем разряде имеют единицу. Следовательно, первое проверочное равенство должно включать символы 1, 3, 5 и 7-го разрядов;

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

Аналогично находим и третье равенство:

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

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

Поскольку построенный код имеет минимальное хэммингово расстояние d_min = =3, он в соответствии с (6.15) может использоваться с целью обнаружения единичных и двойных ошибок. Обращаясь к табл. 6.6, легко убедиться, что сумма любых двух опознавателей единичных ошибок дает ненулевой опознаватель, что и является признаком наличия ошибки.

Пример 6.5. Построим групповой код объемом 15 слов, способный исправлять единичные и обнаруживать двойные ошибки.

В соответствии с (6.17) код должен обладать минимальным хэмминговым расстоянием, равным 4. Такой код можно построить в два этапа. Сначала строим код заданного объема, способный исправлять единичные ошибки. Это код Хэмминга (7, 4). Затем добавляем еще один проверочный разряд, который обеспечивает четность числа единиц в разрешенных комбинациях.

Таким образом, получаем код (8, 4). В процессе кодирования реализуются соотношения:

Обозначив синдром кода (7, 4) через S_i, результат общей проверки на четности через

и пренебрегая возможностью

возникновения ошибок кратности 3 и выше, запишем алгоритм декодирования:

при S₁ = 0 и S₂ = 0 ошибок нет;

при S₁=0 и S₂ = 1 ошибка в восьмом разряде;

при S₁=0 и S₂ = 0 двойная ошибка (коррекция блокируется, посылается запрос повторной передачи),

при S₁=0 и S₂=1 одиночная ошибка (осуществляется ее исправление).

Пример 6.6. Используя табл. 6.6, составим правила построения кода (8, 2), исправляющего все одиночные и двойные ошибки.

Усекая табл. 6.5 на восьмом разряде, найдем следующие проверочные равенства:

Соответственно правила построения кода выразим соотношениями

Отметим, что для построенного кода d_min=5, и, следовательно, он может использоваться обнаружения ошибок кратности от 1 до 4.

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

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

Мажоритарное декодирование тоже базируется на системе проверочных равенств. Система последовательно может быть разрешена относительно каждой из независимых переменных, причем в силу избыточности это можно сделать не единственным способом.

Любой символ a_i, выражается d (минимальное кодовое расстояние) различными независимыми способами в виде линейных комбинаций других символов. При этом может использоваться тривиальная проверка а_i = а_i. Результаты вычислений подаются на соответствующий этому символу мажоритарный элемент. Последний представляет собой схему, имеющую d входов и один выход, на котором появляется единица, когда возбуждается больше половины его входов, и нуль, когда возбуждается число таких входов меньше половины. Если ошибки отсутствуют, то проверочные равенства не нарушаются, и на выходе мажоритарного элемента получаем истинное значение символа. Если число проверок d^2s+1 и появление ошибки кратности s и менее не приводит к нарушению более s проверок, то правильное решение может быть принято по большинству неискаженных проверок. Чтобы указанное условие выполнялось, любой другой символ a_j(j неравно i) не должен входить более чем в одно проверочное равенство. В этом случае мы имеем дело с системой разделенных проверок.

Пример 6.7. Построим систему разделенных проверок для декодирования информационных символов рассмотренного ранее группового кода (8, 2).

Поскольку код рассчитан на исправление любых единичных и двойных ошибок, число проверочных равенств для определения каждого символа должно быть не менее 5. Подставив в равенства (6.26 а) и (6.26 б) значения a₈, полученные из равенств (6.26д) и (6.26е), и записав их относительно а₅ совместно с равенствами (6.26 в) и (6.26г) и тривиальным равенством a₅ = a₅, получим следующую систему разделенных проверок для символа а₅:

Для символа а₈ систему разделенных проверок строим аналогично

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

Транспонированной матрицей к матрице А называют матрицу, строками которой являются столбцы, а столбцами строки матрицы А:

Матрицу размерности nxn называют квадратной матрицей порядка n. Квадратную матрицу, у которой по одной из диагоналей расположены только единицы, а все остальные элементы равны нулю, называют единичной матрицей I. Суммой двух матриц А = |а_ij| и В = |b_ij| размерности lxn называют матрицу размерности lxn:

Умножение матрицы Α = |а_ij| размерности lxn на скаляр с дает матрицу размерности lxn:

Матрицы А == |а_ij| размерности lxn и В = |b_ij| размерности nxm могут быть перемножены, причем элементами C_ik матрицы — произведения размерности lxm являются суммы произведений элементов l-й строки матрицы А на соответствующие элементы k-ro столбца матрицы В:

В теории кодирования элементами матрицы являются элементы некоторого поля GF(P), а строки и столбцы матрицы рассматриваются как векторы. Сложение и умножение элементов матриц осуществляется по правилам поля GF(P).

Пример 6.8. Вычислим произведение матриц с элементами из поля GF(2):

Элементы C_ik матрицы произведения М=М₁М₂ будут равны:

Следовательно,

Зная закон построения кода, определим все множество разрешенных кодовых комбинаций. Расположив их друг под другом, получим матрицу, совокупность строк которой является подпространством векторного пространства η -разрядных кодовых комбинаций (векторов) из элементов поля GF(P). В случае двоичного (n, k)-кода матрица насчитывает n столбцов и 2к-1 строк (исключая нулевую). Например, для рассмотренного ранее кода (8, 2), исправляющего все одиночные и двойные ошибки, матрица имеет вид:

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

Совокупность векторов V₁, V₂, V₃,..., V_n называют линейно зависимой, когда существуют скаляры с₁...с_n (не все равные нулю), при которых

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

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

Среди 2k — 1 ненулевых двоичных кодовых комбинаций — векторов их только k. Например, для кода (8, 2)

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

Если порождающая матрица содержит k строк по n элементов поля GF(q), то код называют (n, k)-кодом. В каждой комбинации (n, k)-кода k информационных символов и n — k проверочных. Общее число разрешенных кодовых комбинаций (исключая нулевую) Q == qk-1.

Зная порождающую матрицу кода, легко найти разрешенную кодовую комбинацию, соответствующую любой последовательности А_ki из k информационных символов. Она получается в результате умножения вектора А_ki на порождающую матрицу М_{n, k}:

Найдем, например, разрешенную комбинацию кода (8, 2), соответствующую информационным символам а₅=1, а₈=1:

Пространство строк матрицы остается неизменным при выполнении следующих элементарных операций над строками: 1) перестановка любых двух строк; 2) умножение любой строки на ненулевой элемент поля; 3) сложение какой-либо строки с произведением другой строки на ненулевой элемент поля, а также при перестановке столбцов.

Если образующая матрица кода M₂ получена из образующей матрицы кода Μ 1 с помощью элементарных операций над строками, то обе матрицы порождают один и тот же код. Перестановка столбцов образующей матрицы кода приводит к образующей матрице эквивалентного кода. Эквивалентные коды весьма близки по своим свойствам. Корректирующая способность таких кодов одинакова.

Для анализа возможностей линейного (n, k)-кода, а также для упрощения процесса кодирования удобно, чтобы порождающая матрица (M_{n, k}) состояла из двух матриц: единичной матрицы размерности kXk и дописываемой справа матрицы-дополнения (контрольной подматрицы) размерности k*(n-k), которая соответствует n — k проверочным разрядам:

Разрешенные кодовые комбинации кода с такой порождающей матрицей отличаются тем, что первые k символов в них совпадают с исходными информационными, а проверочными оказываются (n — k) последних символов.

Действительно, если умножим вектор-строку А_ki = (a₁ a₂...a_i...a_n) на матрицу получим

вектор

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

Коды, удовлетворяющие этому условию, называют систематическими. Для каждого линейного кода существует эквивалентный систематический код.

Как следует из (6.27), (6.28), информацию о способе построения такого кода содержит матрица-дополнение. Если правила построения кода (уравнения кодирования) известны, то значения символов любой строки матрицы-дополнения получим, применяя эти правила к символам соответствующей строки единичной матрицы.

Пример 6.9. Запишем матрицы I_k, P_{k, n-k} и M_{n, k} для двоичного кода (7, 4)

Единичная матрица на четыре разряда имеет вид

Один из вариантов матрицы дополнения можно записать, используя соотношения (6.25)

Тогда для двоичного кода Хэмминга имеем·

Запишем также матрицу для систематического кода (7, 4)·

В свою очередь, по заданной матрице-дополнению P_{k, n-k} можно определить равенства, задающие правила построения кода. Единица в первой строке каждого столбца указывает на то, что в образовании соответствующего столбцу проверочного разряда участвовал первый информационный разряд. Единица в следующей строке любого столбца говорит об участии в образовании проверочного разряда второго информационного разряда и т. д.

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

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

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

Синтезируем таким путем образующую матрицу двоичного систематического кода (7, 4) с минимальным кодовым расстоянием d = 3.

В каждой вектор - строке матрицы - дополнения согласно сформулированному условию (при l= 1) должно быть не менее двух единиц. Среди трехразрядных векторов таких имеется четыре: 011, 110, 101, 111.

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

Нетрудно убедиться, что при суммировании нескольких строк такой матрицы (l> 1) получим вектор-строку, содержащую не менее d = 3 ненулевых символов.

Имея образующую матрицу систематического кода Μ n, k = [I_k P_{k, n-k}], можно построить так называемую проверочную (контрольную) матрицу Η размерности (n---k)Xn:

При умножении неискаженного кодового вектора А_ni на матрицу, транспонированную к матрице Н, получим вектор, все компоненты которого равны нулю:

Каждая компонента S, является результатом проверки справедливости соответствующего уравнения декодирования:

В общем случае, когда кодовый вектор A_ni = (a₁, a₂,...ai,..., a_k, a_k+1,...a_j,..., a_n) искажен вектором ошибки ), умножение вектора (A_ni + ξ _ni) на матрицу Н^t дает ненулевые компоненты:

Отсюда видно, что ι представляют собой символы, зависящие только от вектора ошибки, а вектор S = (S_k+1, S_k+2,..., S_j,...S_n) является не чем иным как опознавателем ошибки (синдромом).

Для двоичных кодов (операция сложения тождественна операции вычитания) проверочная матрица имеет вид

Пример 6.10. Найдем проверочную матрицу Η для кода (7, 4) с образующей матрицей М:

Определим синдромы в случаях отсутствия и наличия ошибки в кодовом векторе 1100011.

Выполним транспонирование матрицы Р_{4, 3}

Запишем проверочную матрицу:

Умножение на Н^t неискаженного кодового вектора 1100011 дает нулевой синдром:

При наличии в кодовом векторе ошибки, например, в 4 м разряде (1101011) получим

Следовательно, вектор-строка 111 в данном коде является опознавателем (синдромом) ошибки в четвертом разряде. Аналогично можно найти и синдромы других ошибок. Множество всех опознавателей идентично множеству опознавателей кода Хэмминга (7, 4), но сопоставлены они конкретным векторам ошибок по-иному, в соответствии с образующей матрицей данного (эквивалентного) кода.

§ 6.5. ТЕХНИЧЕСКИЕ СРЕДСТВА КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДЛЯ ГРУППОВЫХ КОДОВ

Кодирующее устройство строится на основании совокупности равенств, отражающих правила построения кода. Определение значений символов в каждом из n-k проверочных разрядов в кодирующем устройстве осуществляется посредством сумматоров по модулю два.

На каждый разряд сумматора (кроме первого) используется четыре элемента И (вентиля) и два элемента ИЛИ.

Сумматор по модулю два выпускают в виде отдельного логического элемента, который на схеме изображается прямоугольником с надписью внутри — М2.

Приведем несколько примеров реализации кодирующих и декодирующих устройств групповых кодов.

Пример 6.11. Рассмотрим техническую реализацию кода (7, 4), имеющего целью исправление одиночных ошибок.

Правила построения кода определяются равенствами

Схема кодирующего устройства приведена на рис 6.7.

Кодовая комбинация, возможно содержащая ошибку, поступает на n-разрядный приемный регистр (на рис 6.8 триггеры Тг1—Тг. По окончании переходного процесса в триггерах с блока управления на каждый из сумматоров (С1-С3) поступает импульс опроса.

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

Таблица 6.7.

С некоторой задержкой формируются выходные импульсы сумматоров С1, С2 Сз, которые устанавливают триггеры проверочных разрядов в положение 0 или 1 в соответствии с приведенными выше равенствами. Например, в нашем случае ко входам сумматора C₁ подводится информация, записанная в 3, 5 и 7 разрядах и, следовательно, триггер Tг1 первого проверочного разряда устанавливается в положение 1, аналогично триггер Тг2 устанавливается в положение 0, а триггер Тг4 — в положение 1.

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

Таблица 6.8.

Рассмотрим теперь схему декодирования и коррекции ошибок (рис 6.8), строящуюся на основе совокупности проверочных равенств. Для кода (7 4) они имеют вид

Выходные импульсы сумматоров устанавливают в положение 0 или 1 триггеры регистра опознавателей. Если проверочные равенства выполняются, все триггеры регистра опознавателей устанавливаются в положение 0, что соответствует отсутствию ошибок. При наличии ошибки в регистр опознавателей запишется опознаватель этого вектора ошибки. Дешифратор ошибки DC ставит в соответствие множеству опознавателей множество векторов ошибок. При опросе выходных вентилей дешифратора сигналы коррекции поступают только на те разряды, в которых вектор ошибки, соответствующий записанному на входе опознавателю, имеет единицы. Сигналы коррекции воздействуют на счетные входы триггеров. Последние изменяют свое состояние, и, таким образом, ошибка исправлена. На триггеры проверочных разрядов импульсы коррекции можно не посылать, если после коррекции информация списывается только с информационных разрядов. Для кода Хэмминга (7, 4) любой опознаватель представляет собой двоичное трехразрядное число, равное номеру разряда приемного регистра, в котором записан ошибочный символ

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

Таблица 6.9

По результатам опроса сумматоров получаем на выходе С₁ на выходе С₂ на выходе С₃

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

Пример 6.12. Реализуем мажоритарное декодирование для группового кода (8, 2), рассчитанного на исправление двойных ошибок (см. § 6.4).

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

Схема декодирования представлена на рис. 6.9. На входах мажоритарных элементов указаны сигналы, соответствующие случаю поступления из канала связи кодовой информации, искаженной в обоих информационных разрядах (5-м и 8-м). Реализуя принцип решения по большинству, мажоритарные элементы восстанавливают на выходе правильные значения информационных символов.

§ 6.6. ПОСТРОЕНИЕ ЦИКЛИЧЕСКИХ КОДОВ

Общие понятия и определения. Любой групповой код (n, k)может быть записан в виде матрицы, включающей k линейно независимых строк по n символов и, наоборот, любая совокупность k линейно независимых n-разрядных кодовых комбинаций может рассматриваться как образующая матрица некоторого группового кода. Среди всего многообразия таких кодов можно выделить коды, у которых строки образующих матриц связаны дополнительным условием цикличности.

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

удовлетворяющие этому условию, получили название циклических кодов.

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

Число возможных циклических (n, k)-кодов значительно меньше числа различных групповых (n, k)-кодов.

При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной х. Показатели степени у x соответствуют номерам разрядов (начиная с нулевого), а коэффициентами при x в общем случае являются элементы поля GF(q). При этом наименьшему разряду числа соответствует фиктивная переменная х° = 1. Многочлен с коэффициентами из поля GF(q) называют многочленом над полем GF(q). Так как мы ограничиваемся рассмотрением только двоичных кодов, то коэффициентами при x будут только цифры 0 и 1. Иначе говоря, будем оперировать с многочленами над полем GF(2).