3.2.3. Заранее выбранные покрывающие множества

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

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

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

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

3.2.3.1. Нижние границы для числа покрывающих множеств. Грубая нижняя граница для числа различных проверочных (или информационных) множеств, необходимых для исправления

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

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

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

3.2.3.2. Методы нахождения покрывающих множеств. Возможная процедура получения покрывающего множества состоит в последовательном порождении множества наборов веса каждый из которых должен покрывать (если можно) некоторое число ранее не покрытых комбинаций ошибок. Предположим, например, что задан -код и требуется определить возможно меньшее число покрытий, исправляющих все двойные ошибки. Предположим, что каждый набор из восьми позиций может служить проверочным множеством. В качестве первых двух наборов выберем позиции Поскольку они не перекрываются, каждый из них покрывает 28 комбинаций ошибок и 64 комбинации остаются непокрытыми. Добавим теперь множество, покрывающее возможно большее число дополнительных комбинаций. Такому условию удовлетворяет любое множество, содержащее 4 из первых восьми и 4 из последних восьми позиций. Таким образом, разумным представляется выбор множества Продолжая таким же образом, приходим к покрытиям, показанным в табл. 3.2. Следовательно, все двойные ошибки могут быть покрыты шестью проверочными множествами. Вычисляя правую часть (3.2), получаем так что это решение является оптимальным. Конечно, нельзя гарантировать, что указанные множества позиций могут служить проверочными множествами любого заданного кода. Один из способов преодолеть возникающие здесь трудности состоит в изменении проверочных множеств с помощью перестановки позиций в кодовом слове. Например, перестановка позиций 4 и 10 приводит к проверочным множествам, показанным в

Таблица 3.2. (см. скан) Покрытия для -кода

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

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

Таблица 3.3. (см. скан) Видоизмененное покрытие для -кода

Баумерт, Мак-Элис и Соломон [16] показали, что выколотый -код Соломона — Стиффлера можно использовать для нахождения покрывающего множества -кода, исправляющего пять ошибок. (Этот код получается выкалыванием -кода максимальной длины.) Они заметили, во-первых, что для любых пяти позиций -кода существует по крайней мере одно кодовое слово, у которого эти позиции являются нулевыми. И, во-вторых, кодовое расстояние -кода равно 24. Любое кодовое слово, вес которого превосходит 24, может быть сведено к кодовому слову веса 24, причем свойство покрытия нулями будет сохраняться. Таким образом, можно использовать 63 ненулевых кодовых слова для построения покрывающего множества, выбирая в качестве позиций проверочного множества нулевые позиции соответствующего кодового слова. Из (3.2)

следует, что . В случае, рассмотренном в [16], не все 63 ненулевых кодовых слова приводят к разрешенным информационным множествам, и нужно добавить 29 дополнительных множеств, используя методы, описанные в п. 3.2.3.3. Таким образом, общее число множеств равно 92, что оказывается вполне приемлемым во многих случаях.

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

Использование вспомогательного кода для построения покрывающих множеств оказывается успешным для ряда кодов со скоростью 1/2. Например, существует -код с кодовым расстоянием 6, который покрывает все комбинации из трех ошибок в -коде с помощью пятнадцати множеств. Граница дает Существуют также -код и -код с кодовым расстоянием 16 каждый, которые могут служить для покрытия всех комбинаций из четырех или пяти ошибок в -коде с помощью 31 и 63 множеств соответственно. Нижняя граница в каждом из этих случаев дает 30 и 62. Таким образом, эти вспомогательные коды приводят к очень хорошим решениям.

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

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

для любого целого Инвариантность относительно перестановок вида -это свойство цикличности рассматриваемого/кода, т. е. свойство, согласно которому любой циклический сдвиг кодового слова является кодовым словом. Инвариантность относительно перестановок вида (3.4) вытекает из того, что

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

Предположим, например, что

является кодовым словом циклического слова длиной 7 над Тогда

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

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

Наряду с двумя указанными имеется ряд других способов перестановок, оставляющих инвариантными отдельные коды. (Подробное обсуждение содержится в книге Берлекэмпа [2], т. 360-369.) Однако до сих пор это свойство почти не использовалось. Среди всех возможных перестановок циклические оказываются наиболее полезными, и все обсуждаемые в этой главе примеры основаны на их свойствах. В статье [17] исследованы декодеры, построенные согласно (3.3) и (3.4), и, обратившись к этой статье, читатель найдет дальнейшие подробности.

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

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

Пример, в котором нужны только циклические перестановки, показан на рис. 3.4. Схема декодера очень похожа на схему декодера Меггитта, приведенную на рис. 3.2. В рассматриваемом примере «устройство распознавания» программируется таким образом, чтобы выдавать отклик на любую комбинацию ошибок веса 2 или менее. После вычисления первоначального синдрома регистры синдрома и памяти одновременно сдвигаются до тех пор, пока не будет обнаружен синдром веса 2. В этот момент цель обратной связи отключается и содержимое регистра синдрома посимвольно складывается со сдвинутой принятой последовательностью. Затем декодер сдвигается на оставшуюся часть цикла и декодированное слово поступает к пользователю. Читатель должен убедиться, что любая комбинация из двух ошибок всегда может быть сдвинута на позиции между 0 и 7, так что декодер исправляет все такие комбинации. Заметим также, что аналогично декодеру Меггитта, исправляющему пакеты ошибок, фаза регистра синдрома сдвинута на восемь позиций относительно фазы регистра памяти. Такой сдвиг достигается тем, что исправления вводятся на выход восьмой ячейки регистра памяти.

Рис. 3.4. Перестановочный декодер для -кода, исправляющего двойные ошибки, с порождающим многочленом

Рис. 3.5. Представление всех комбинаций трех ошибок, которые должны быть покрыты в циклическом коде длиной 15

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

Из рис. 3.5 легко увидеть, что все тройные ошибки, кроме одной, имеющей координаты 0, 5, 10, покрываются проверочным множеством На этой стадии существует несколько различных возможностей. Одна из них состоит в построении второго проверочного множества, которое совместно с первым будет покрывать все возможные ошибки. Вторая состоит в попытке найти одно проверочное множество, которое будет покрывать все ошибки. Третья возможность — в использовании первоначального проверочного множества и попытке видоизменить алгоритм декодирования таким образом, чтобы учесть возможность существования одной ошибки вне проверочного множества. Для изучения этих возможностей полезно иметь проверочную матрицу кода. Эту матрицу легко получить из генератора кода

Она имеет вид

Для реализации первой возможности нужно лишь потребовать, чтобы второй проверочное множество содержало элементы Этого можно добиться, переставляя десятый столбец проверочной матрицы с любым из первых десяти, кроме, конечно, столбцов 0 и 5. Можно, например, выбрать столбец 8. Новая проверочная матрица получается добавлением строки 8 к строкам 0, 1, 2, 4 и 5. Аналогичным преобразованием можно получить новый синдром из первоначального.

Хотя и не ставилась такая задача, однако оказывается, что построенное проверочное множество покрывает не только комбинацию но и все остальные, указанные на рис. 3.5. Таким образом, используя одно это проверочное множество, реализуем вторую возможность.

Для реализации третьей возможности следует заметить, что каждый раз, когда на позиции 10 возникает ошибка, десятый столбец проверочной матрицы прибавляется к синдрому, вызываемому остальными ошибками. Следовательно, если на позиции 10 возникла ошибка, ее влияние на синдром можно устранить, добавляя к нему столбец 10. Полученный таким образом синдром будет соответствовать двум ошибкам или одной на позициях 0 и 5. Следовательно, для реализации третьей возможности следует вначале вычислить оба синдрома. Первый синдром нужно проверить на наличие комбинаций веса 3 или менее, а второй — на наличие комбинаций веса 2 или менее. Интересно отметить, что видоизмененный синдром будет покрывать все комбинации из трех ошибок, и можно использовать только его. Обычно это будет не так, и следует отдельно рассматривать случаи наличия и отсутствия ошибок вне проверочного множества.

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

Рис. 3.6. Общий декодер для -кода, исправляющего тройные ошибки

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

Возможность 1:

Возможность 2:

Возможность 3:

такие же, как в первом случае (но не используются),

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

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

Имеется интересный класс кодов, для которых этот алгоритм особенно полезен в случаях, когда числошибок не очень велико. Это коды Рида — Соломона (PC) над которые были

Рис. 3.7. Комбинации трех ошибок, покрываемые по крайней мере одним из трех множеств для -кода Рида-Соломона

введены в гл. 2 и будут более подробно обсуждаться в гл. 5. Здесь достаточно заметить, что эти коды являются циклическими и их длина равна Они обладают свойством, согласно которому любая комбинация из или менее ошибок может быть исправлена, и для исправления каждого символа требуется два проверочных символа. Так, кодом, исправляющим ошибочных символов, будет -код. Кроме того, интересное свойство этих кодов состоит в том, что любые позиций могут быть выбраны в качестве проверочного множества. Поэтому можно ограничиться решением задачи о покрытиях. В качестве примера рассмотрим -код исправляющий три или менее ошибок символов. Можно показать, что проверочные множества после подходящего циклического сдвига могут покрыть любую комбинацию трех ошибок. Множества выбирались последовательно таким образом, чтобы каждое следующее множество добавляло максимально возможное число новых комбинаций ошибок. Все комбинации ошибок, покрываемые множеством А, все комбинации, покрываемые В, но не покрываемые А, и все комбинации, покрываемые С, но не покрываемые ни А, ни В, показаны на рис. 3.7.