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

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

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

или

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

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

Общее число различных исправляемых ошибок для каждой разрешенной комбинации составляет (см. рис. 6.2).

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

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

или

Эта верхняя оценка найдена Хэммингом. Для некоторых конкретных значений кодового расстояния d соответствующие Q указаны в табл. 6.1.

Таблица 6.1

Коды, для которых в приведенном соотношении достигается равенство, называют также плотноупакованными.

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

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

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

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

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

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

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

Множества, для которых определены некоторые алгебраические операции, называют алгебраическими системами. Под алгебраической операцией понимают однозначное сопоставление двум элементам некоторого третьего элемента по определенным правилам. Обычно основную операцию называют сложением (обозначают а + b = с) или умножением (обозначают а∙ b=с), а обратную ей — вычитанием или делением, даже если эти операции проводятся не над числами и неидентичны соответствующим арифметическим операциям.

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

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

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

2. Для любых трех элементов группы а, b и с удовлетворяется равенство (если основная операция — сложение) и равенство (если основная операция — умножение).

3. В любой группе G_n существует однозначно определенный элемент, удовлетворяющий при всех значениях а из G_n условию (если основная операция — сложение) или условию (если основная операция — умножение).

В первом случае этот элемент называют нулем и обозначают символом 0, а во втором — единицей и обозначают символом 1.

4. Всякий элемент а группы обладает элементом, однозначно определенным уравнением а +(- а) = - а + а = 0 (если основная операция сложение) или уравнением (если основная операция — умножение).

В первом случае этот элемент называют противоположным и обозначают (- а), а во втором — обратным и обозначают а ^-1.

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

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

Чтобы рассматриваемое нами множество n-разрядных кодовых комбинаций было конечной группой, при выполнении основной операции число разрядов в результирующей кодовой комбинации не должно увеличиваться. Этому условию удовлетворяет операция символического поразрядного сложения по заданному модулю q (q — простое число), при которой цифры одинаковых разрядов элементов группы складываются обычным порядком, а результатом сложения считается остаток от деления полученного числа на модуль q.

При рассмотрении двоичных кодов используется операция сложения по модулю 2. Результатом сложения цифр данного разряда является 0, если сумма единиц в нем четна, и 1, если сумма единиц в нем нечетна, например:

Выбранная нами операция коммутативна, поэтому рассматриваемые группы будут абелевыми.

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

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

Первое множество не является группой, так как не содержит нулевого элемента.

Второе множество не является группой, так как не выполняется условие замкнутости, например сумма по модулю 2 комбинаций 1101 и 1110 дает комбинацию 0011, не принадлежащему исходному множеству.

Третье множество удовлетворяет всем перечисленным условиям и является группой.

Подмножества группы, являющиеся сами по себе группами относительно операции, определенной в группе, называют подгруппами. Например, подмножество трехразрядных кодовых комбинаций: 000, 001, 010, 011 образуют подгруппу указанной в примере группы трехразрядных кодовых комбинаций.

Пусть в абелевой группе G_n задана определенная подгруппа А. Если В — любой не входящий в А элемент из G_n, то суммы (по модулю 2) элементов В с каждым из элементов подгруппы А образуют смежный класс группы G_n по подгруппе А, порождаемый элементом В.

Элемент В, естественно, содержится в этом смежном классе, так как любая подгруппа содержит нулевой элемент. Взяв последовательно некоторые элементы В_j группы, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по подгруппе А.

Элементы B_j называют образующими элементами смежных классов подгруппы.

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

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

Разложение выполняем в соответствии с табл. 6.2.

Таблица 6.2

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

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

Таблица 6.3

Кольцом называют множество элементов R, на котором определены две операции (сложения и умножения), такие, что:

1) множество R является коммутативной группой по сложению;

2) произведение элементов a R и b R есть элемент R (замкнутость по отношению к умножению);

3) для любых трех элементов а, b и с из R справедливо равенство a(bc) = (ab)c (ассоциативный закон для умножения);

4) для любых трех элементов а, b и с из R выполняются соотношения а(b+с) = =ab+ас и (b+c)a = bа+са (дистрибутивные законы).

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

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

Полем F называют множество по крайней мере двух элементов, в котором определены две операции — сложение и умножение, и выполняются следующие аксиомы:

1) множество элементов образует коммутативную группу по сложению;

2) множество ненулевых элементов образует коммутативную группу по умножению;

3) для любых трех элементов множества а, b, с выполняется соотношение (дистрибутивный закон)

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

Поле GF(P), состоящее из конечного числа элементов Р, называют конечным полем или полем Галуа. Для любого числа Р, являющегося степенью простого числа q, существует поле, насчитывающее Р элементов. Например, совокупность чисел по модулю q, если q — простое число, является полем.

Поле не может содержать менее двух элементов, поскольку в нем должны быть по крайней мере единичный элемент относительно операции сложения (0) и единичный элемент относительно операции умножения (1). Поле, включающее только 0 и 1, обозначим GF (2). Правила сложения и умножения в поле с двумя элементами следующие:

Двоичные кодовые комбинации, являющиеся упорядоченными последовательностями из n элементов поля GF (2), рассматриваются в теории кодирования как частный случай последовательностей из n элементов поля GF(P). Такой подход позволяет строить и анализировать коды с основанием, равным степени простого числа.

В общем случае суммой кодовых комбинаций A_j, и A_i называют комбинацию A_f = A_i+A_j, в которой любой символ A_k (k=1, 2,..., n) представляет собой сумму k-x символов исходных комбинаций, причем суммирование производится по правилам поля GF(P). При этом вся совокупность n-разрядных кодовых комбинаций оказывается абелевой группой.

В частном случае, когда основанием кода является простое число q, правило сложения в поле GF(q) совпадает с правилом сложения по заданному модулю q.

Линейный код как подпространство линейного векторного пространства. В рассмотренных алгебраических системах (группа, кольцо, поле) операции относились к одному классу математических объектов (элементов). Такие операции называют внутренними законами композиции элементов.

В теории кодирования широко используются модели, охватывающие два класса математических объектов (например, L и Ω). Помимо внутренних законов композиции в них задаются внешние законы композиции элементов, по которым любым элементам ω Ω и a L ставится в соответствие элемент c L.

Линейным векторным пространством над полем элементов F (скаляров) называют множество элементов V (векторов), если для него выполняются следующие аксиомы:

1) множество V является коммутативной группой относительно операции сложения;

2) для любого вектора ν из V и любого скаляра с из F определено произведение с v, которое содержится в V (замкнутость по отношению умножения на скаляр);

3) если u и ν из V векторы, а с и d из F скаляры, то справедливо (дистрибутивные законы);

4) если ν — вектор, а с и d — скаляры, то (cd)v = c(dv) и 1 · ν = ν (ассоциативный закон для умножения на скаляр).

Выше было определено правило поразрядного сложения кодовых комбинаций, при котором вся их совокупность образует абелеву группу. Определим теперь операцию умножения последовательности из n элементов поля GF(P) (кодовой комбинации) на элемент поля а _i из GF(P) аналогично правилу умножения вектора на скаляр:

[умножение элементов производится по правилам поля GF(P)].

Поскольку при выбранных операциях дистрибутивные законы и ассоциативный закон (п. 3, 4) выполняются, все множество n-разрядных кодовых комбинаций можно рассматривать как векторное линейное пространство над полем GF(P), а кодовые комбинации — как его векторы.

В частности, при двоичном кодировании векторы состоят из элементов поля GF (2) (т. е. 0 и 1). Сложение проводят поразрядно по модулю 2. При умножении вектора на один элемент поля (1) он не изменяется, а умножение на другой (0) превращает его в единичный элемент векторного пространства, обозначаемый символом 0= (0 0...0).

Если в линейном пространстве последовательностей из n элементов поля GF(P) дополнительно задать операцию умножения векторов, удовлетворяющую определенным условиям (ассоциативности, замкнутости, билинейности по отношению к умножению на скаляры), то вся совокупность n-разрядных кодовых комбинаций превращается в линейную коммутативную алгебру над полем коэффициентов GF(P).

Подмножество элементов векторного пространства, которое удовлетворяет аксиомам векторного пространства, называют подпространством.

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

В случае двоичного кодирования такого подпространствo комбинаций над полем GF (2) образует любая совокупность двоичных кодовых комбинаций, являющаяся подгруппой группы всех n-разрядных двоичных кодовых комбинаций. Поэтому любой двоичный линейный код является групповым.

§ 6.4. ПОСТРОЕНИЕ ДВОИЧНОГО ГРУППОВОГО КОДА

Построение конкретного корректирующего кода производят, исходя из требуемого объема кода Q, т. е. необходимого числа передаваемых команд или дискретных значений измеряемой величины и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи. Вектором ошибки называют n-разрядную двоичную последовательность, имеющую единицы в разрядах, подвергшихся искажению, и нули во всех остальных разрядах. Любую искаженную кодовую комбинацию можно рассматривать теперь как сумму (или разность) по модулю 2 исходной разрешенной кодовой комбинации и вектора ошибки.

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

Каждой из 2^k-1 ненулевых комбинаций k-разрядного безызбыточного кода нам необходимо поставить в соответствие комбинацию из n символов. Значения символов в n — k проверочных разрядах такой комбинации устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.

Поскольку множество 2^k комбинаций информационных символов (включая нулевую) образует подгруппу группы всех n-разрядных комбинаций, то и множество 2^k n-разрядных комбинаций, полученных по указанному правилу, тоже является подгруппой группы n-разрядных кодовых комбинаций. Это множество разрешенных кодовых комбинаций и будет групповым кодом.

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

Разложим группу 2ⁿ всех n-разрядных комбинаций на смежные классы по подгруппе 2^k разрешенных n-разрядных кодовых комбинаций, проверочные разряды в которых еще не заполнены. Помимо самой подгруппы кода в разложении насчитывается 2^n-k —1 смежных классов. Элементы каждого класса представляют собой суммы по модулю 2 комбинаций кода и образующих элементов данного класса. Если за образующие элементы каждого класса принять те наиболее вероятные для заданного канала связи вектора ошибок, которые должны быть исправлены, то в каждом смежном классе сгруппируются кодовые комбинации, получающиеся в результате воздействия на все разрешенные комбинации определенного вектора ошибки. Для исправления любой полученной на выходе канала связи кодовой комбинации теперь достаточно определить, к какому классу смежности она относится. Складывая ее затем (по модулю 2) с образующим элементом этого смежного класса, получаем истинную комбинацию кода.

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

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

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

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

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

Если, например, необходимо исправить все одиночные независимые ошибки, то исправлению подлежат n ошибок:

Различных ненулевых опознавателей должно быть не менее n. Необходимое число проверочных разрядов, следовательно, должно определяться из соотношения

или

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

В общем случае для исправления всех независимых ошибок кратности до s включительно получаем

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

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

Составление таблицы опознавателей. Начнем для простоты с установления опознавателей для случая исправления одиночных ошибок. Допустим, что необходимо закодировать 15 команд. Тогда требуемое число информационных разрядов равно четырем. Пользуясь соотношением , определяем общее число разрядов кода, а следовательно, и число ошибок, подлежащих исправлению (n = 7). Три избыточных разряда позволяют использовать в качестве опознавателей трехразрядные двоичные последовательности.

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

Таблица 6.4

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

Коды, в которых опознаватели устанавливаются по указанному принципу, известны как коды Хэмминга.

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

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

В качестве опознавателя одиночной ошибки в третьем разряде можно взять только трехразрядную комбинацию 0...0100, так как множество двухразрядных комбинаций уже исчерпано. Подлежащий исправлению вектор ошибки 0...0101 также можно рассматривать как результат суммарного воздействия двух векторов ошибок 0...0100 и 0...001 и, следовательно, ему должен быть поставлен в соответствие опознаватель, представляющий собой сумму по модулю 2 опознавателей этих ошибок, т.е. 0...0101.

Аналогично находим, что опознавателем вектора ошибки 0...0110 является комбинация 0...0110.

Определяя опознаватель для одиночной ошибки в четвертом разряде, замечаем, что еще не использована одна из трехразрядных комбинаций, а именно 0...0111. Однако, выбирая в качестве опознавателя единичной ошибки в i -м разряде комбинацию с числом разрядов, меньшим i, необходимо убедиться в том, что для всех остальных подлежащих исправлению векторов ошибок, имеющих единицы в ί -м и более младших разрядах, получатся опознаватели, отличные от уже использованных. В нашем случае подлежащими исправлению векторами ошибок с единицами в четвертом и более младших разрядах являются:

0...01001, 0...01010, 0...01100.

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

Однако эти комбинации уже использованы в качестве опознавателей других векторов ошибок, а именно: 0...0110, 0...0101, 0...0011.

Следовательно, во избежание неоднозначности при декодировании в качестве опознавателя одиночной ошибки в четвертом разряде следует взять четырехразрядную комбинацию 1000. Тогда для векторов ошибок 0...01001, 0...01010, 0...01100 опознавателями соответственно будут: 0...01001, 0...01010, 0...01100.

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

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

Векторы ошибок Опознаватели

0 010001 0 0110

0 010010 0 01101

0 010100 0 01011

0 011000 0 00111

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