Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.2.3. Заранее выбранные покрывающие множестваПри использовании заранее выбранного покрывающего множества возникают два важных вопроса. Первый из них состоит в том, каково минимальное число различных проверочных множеств, необходимых для исправления данного числа ошибок, второй — как найти эти множества. К сожалению, ни на один из этих вопросов нет вполне удовлетворительного ответа. Даже давно поставленная классическая задача о покрытиях, в которой отбрасывается требование, чтобы данная покрывающая комбинация была также проверочным множеством, является, за исключением немногих случаев, нерешенной. Таким образом, надежда найти оптимальное решение более трудной задачи, в которой налагается указанное дополнительное ограничение, весьма мала. На все эти вопросы можно, однако, найти такие ответы, которые будут приемлемы для практических случаев. Поскольку неизвестно никакой конструктивной процедуры нахождения оптимальных покрывающих множеств, то приходится выбирать некоторую процедуру, которая кажется подходящей в данной ситуации, и определять каким-то образом, насколько разумным оказался полученный результат. При обычном методе здесь вначале требуется найти нижнюю границу для числа требуемых комбинаций. Если полученная оценка кажется разумной, то на следующем этапе методом проб и ошибок или каким-либо другим находят набор множеств, покрывающих все нужные комбинации ошибок, не заботясь пока о том, чтобы эти множества были проверочными. Этот этап обычно следует повторять до тех пор, пока ответ не станет близким к полученной ранее границе или пока число полученных множеств не станет приемлемым по сложности и стоимости требуемого оборудования. Последний этап состоит в проверке требования, чтобы каждое множество было проверочным. На этом последнем этапе обычно оказывается, что почти все покрывающие множества уже являются проверочными. Для завершения этого этапа можно выбрать один из следующих методов: 1) найти дополнительные множества, исправляющие оставшиеся непокрытыми комбинации ошибок; 2) видоизменять имеющийся набор множеств, переставляя символы так, чтобы уменьшить число покрывающих множеств, не являющихся проверочными, или полностью избавиться от таких множеств или 3) видоизменять алгоритм декодирования таким образом, чтобы иметь возможность использовать покрывающие множества, не являющиеся проверочными. Наиболее удовлетворительное решение обычно получается при комбинировании второго и третьего методов. Эта задача затрудняется еще и тем, что минимизация числа требуемых проверочных множеств взаимосвязана с минимизацией затрат (вычислений и памяти), требуемых для использования этих проверочных множеств. Последнее замечание особо важно для циклических кодов, когда часто оказывается возможным породить последовательность различных проверочных множеств некоторой простой операцией, например циклическим сдвигом кодового слова. В нескольких следующих подразделах будут приведены границы для минимального числа проверочных множеств, необходимых для того, чтобы покрыть все комбинации из 3.2.3.1. Нижние границы для числа покрывающих множеств. Грубая нижняя граница для числа различных проверочных (или информационных) множеств, необходимых для исправления фиксированного числа ошибок, получается следующим образом. Предположим, что с помощью
Этот результат может быть улучшен. Шонхейм [15] показал, что более точная граница определяется выражением
где 3.2.3.2. Методы нахождения покрывающих множеств. Возможная процедура получения покрывающего множества состоит в последовательном порождении множества наборов веса Таблица 3.2. (см. скан) Покрытия для табл. 3.3, и можно пытаться выяснить, является ли каждое из указанных покрытий проверочным множеством. Еще один способ преодоления таких трудностей будет описан в подразд. 3.2.3. Рассматривая предыдущий пример, можно заметить, что на каждом шаге наибольшее число новых комбинаций добавляется в том случае, если новое множество отличается от всех предыдущих в возможно большем числе позиций. Отсюда следует, что расстояние между множествами должно быть большим и что задача по рождения покрывающего множества аналогична задаче построения хорошего кода. В самом деле, в некоторых случаях коды с большим кодовым расстоянием являются почти оптимальными покрывающими множествами. Таблица 3.3. (см. скан) Видоизмененное покрытие для Баумерт, Мак-Элис и Соломон [16] показали, что выколотый следует, что В предыдущем примере использовалось свойство, согласно которому для любых пяти позиций существует по крайней мере одно ненулевое кодовое слово с нулевыми символами во всех этих пяти позициях. Это свойство справедливо для любого числа позиций, которое меньше числа информационных символов. В самом деле, если рассматриваемые позиции образуют часть информационного множества, то соответствующие символы, конечно, могут быть сделаны нулевыми в ненулевом кодовом слове. Если не все из указанных символов могут быть заданы независимо друг от друга, то некоторые из них являются линейными комбинациями остальных. Если положить независимые символы равными 0, то все их линейные комбинации также будут нулевыми. Поскольку в любом случае существует по крайней мере один дополнительный независимый символ, который может быть сделан ненулевым, то должно существовать по крайней мере одно ненулевое кодовое слово, заданные Использование вспомогательного кода для построения покрывающих множеств оказывается успешным для ряда кодов со скоростью 1/2. Например, существует Помимо непосредственного использования кода как набора покрывающих множеств его можно также применять для получения списка возможных множеств, из которого можно последовательно выбирать покрывающие множества и при этом быть уверенным, что расстояние между двумя последовательными множествами является большим. 3.2.3.3. Покрытия, порожденные перестановками. В своей первоначальной работе Прейндж также предложил метод построения различных информационных множеств, применимый к любому циклическому коду. Этот метод основан на том, что все циклические коды над
для любого целого
Таким образом, если Предположим, например, что
является кодовым словом циклического слова длиной 7 над
также является кодовым словом. Многочлен Вместо перестановки символов принятого слова можно переставлять столбцы проверочной матрицы. Этого можно добиться либо фактически переставляя столбцы, либо беря подходящие линейные комбинации строк проверочной матрицы, либо, наконец, беря линейные комбинации элементов синдрома, полученного в результате фактического умножения на первоначальную проверочную матрицу. В практических случаях наиболее эффективным является последний способ. Наряду с двумя указанными имеется ряд других способов перестановок, оставляющих инвариантными отдельные коды. (Подробное обсуждение содержится в книге Берлекэмпа [2], т. 360-369.) Однако до сих пор это свойство почти не использовалось. Среди всех возможных перестановок циклические оказываются наиболее полезными, и все обсуждаемые в этой главе примеры основаны на их свойствах. В статье [17] исследованы декодеры, построенные согласно (3.3) и (3.4), и, обратившись к этой статье, читатель найдет дальнейшие подробности. Особенно эффективным оказывается использование циклических перестановок при вычислении синдрома в нормальной форме с помощью регистра сдвига с обратными связями, построенного с помощью ошибок, которая подходящим циклическим сдвигом переводится в пакет, длина которого не превышает Пример, в котором нужны только циклические перестановки, показан на рис. 3.4. Схема декодера очень похожа на схему декодера Меггитта, приведенную на рис. 3.2. В рассматриваемом примере «устройство распознавания» программируется таким образом, чтобы выдавать отклик на любую комбинацию ошибок веса 2 или менее. После вычисления первоначального синдрома регистры синдрома и памяти одновременно сдвигаются до тех пор, пока не будет обнаружен синдром веса 2. В этот момент цель обратной связи отключается и содержимое регистра синдрома посимвольно складывается со сдвинутой принятой последовательностью. Затем декодер сдвигается на оставшуюся часть цикла и декодированное слово поступает к пользователю. Читатель должен убедиться, что любая комбинация из двух ошибок всегда может быть сдвинута на позиции между 0 и 7, так что декодер исправляет все такие комбинации. Заметим также, что аналогично декодеру Меггитта, исправляющему пакеты ошибок, фаза регистра синдрома сдвинута на восемь позиций относительно фазы регистра памяти. Такой сдвиг достигается тем, что исправления вводятся на выход восьмой ячейки регистра памяти.
Рис. 3.4. Перестановочный декодер для
Рис. 3.5. Представление всех комбинаций трех ошибок, которые должны быть покрыты в циклическом коде длиной 15 Несколько бблее сложной структура получается при попытке построить декодер для исправления всех тройных ошибок в циклическом Из рис. 3.5 легко увидеть, что все тройные ошибки, кроме одной, имеющей координаты 0, 5, 10, покрываются проверочным множеством
Она имеет вид
Для реализации первой возможности нужно лишь потребовать, чтобы второй проверочное множество содержало элементы Хотя и не ставилась такая задача, однако оказывается, что построенное проверочное множество покрывает не только комбинацию Для реализации третьей возможности следует заметить, что каждый раз, когда на позиции 10 возникает ошибка, десятый столбец проверочной матрицы прибавляется к синдрому, вызываемому остальными ошибками. Следовательно, если на позиции 10 возникла ошибка, ее влияние на синдром можно устранить, добавляя к нему столбец 10. Полученный таким образом синдром будет соответствовать двум ошибкам или одной на позициях 0 и 5. Следовательно, для реализации третьей возможности следует вначале вычислить оба синдрома. Первый синдром нужно проверить на наличие комбинаций веса 3 или менее, а второй — на наличие комбинаций веса 2 или менее. Интересно отметить, что видоизмененный синдром будет покрывать все комбинации из трех ошибок, и можно использовать только его. Обычно это будет не так, и следует отдельно рассматривать случаи наличия и отсутствия ошибок вне проверочного множества. Схема общего декодера
Рис. 3.6. Общий декодер для определения попадания ошибок в проверочное множество. Через С обозначается Возможность 1:
Возможность 2:
Возможность 3:
Следует отметить, что метод, используемый в третьем случае, может применяться и тогда, когда нужно взять данное покрытие, но указанные позиции не образуют проверочного множества. При этом нужно образовать всевозможные наборы ошибок на позициях, не входящих в проверочное множество, и породить требуемые комбинации. Возможны также и более сложные случаи. Если число ошибок превышает 3, то непосредственная проверка того, все ли комбинации ошибок оказываются покрытыми, становится достаточно громоздкой. Однако комбинации из четырех, пяти и шести ошибок легко исследовать с помощью ЭВМ. Можно, кроме того, видоизменить алгоритм декодирования так, чтобы исправлять некоторые комбинации ошибок, кратность которых превышает кодовое расстояние. В этом случае нужно выбрать число дополнительных покрытий, достаточное для исправления дополнительных комбинаций ошибок. Работа декодера разбивается на два этапа. На первом этапе просматривается принятое слово и находится положение комбинации наименьшего веса. На втором этапе регистр синдрома доходит до этой комбинации и ошибка исправляется. Имеется интересный класс кодов, для которых этот алгоритм особенно полезен в случаях, когда числошибок не очень велико. Это коды Рида — Соломона (PC) над
Рис. 3.7. Комбинации трех ошибок, покрываемые по крайней мере одним из трех множеств введены в гл. 2 и будут более подробно обсуждаться в гл. 5. Здесь достаточно заметить, что эти коды являются циклическими и их длина равна
|
1 |
Оглавление
|