У. Питерсон - Коды, исправляющие ошибки (1267328), страница 53
Текст из файла (страница 53)
жет быть кодовым вектором. Ч. т. д. Оказывается, что можно также обнаруживать и значительную часть более длинных пакетов ошибок. Теорема 8.6. Доля пакетов ошибок длины Ь и — й, которые не могут быть обнаружена циклическим (и, *я) -кодом, равна г/-Ч -~-В((г/ — 1), если Ь = и — й+1, и равна д-! — ы, если Ь- и — й+ 1. Показательство. Рассмотрим пакеты длины Ь, начинающиеся с 1-го символа и заканчиваюгциеся (1+Ь вЂ” 1)-м символом. Каждый из них может быть представлен в виде (г(Х)) = (Х'г,(Х)), где г,(Х) — многочлен степени Ь вЂ” 1. Существует д — 1 способов выбора первого коэффициента, о — 1 способов выбора последнего коэффициента и д способов выбора каждого коэффициента между ними.
Таким образом, существует всего (д — 1)хдь х различных многочленов г| (Х). Ошибка остается необнаруженной тогда н только тогда, когда в разложении многочлена г,(Х) на множители в качестве сомножителя содержится многочлен д(Х), т. е.
г, (Х) = д (Х) Я (Х). Степень д(Х) равна п — й, поэтому степень многочлена Я(Х) должна быть равна Ь вЂ” 1 — (и — й). Если Ь вЂ” 1 = и — й, то 1~(Х) — постоянная величина, отличная от нуля, которая может принимать о — 1 возможных значений. Отношение числа необнаруживаемых пакетов ошибок к общему числу пакетов равно (д — 1)/((су — 1)зсуь — з)= д-ы — ь-и/(у — 1).
Если Ь вЂ” 1) и — я, то первым коэффициентом многочлена Я(Х) может быть любой из д — 1 ненулевых элементов поля, последним коэффициентом также может быть любой из д — 1 ненулевых элементов поля н каждый из д элементов поля может быть любым промежуточным коэффициентом. Имеется, следовательно, всего (д — 1)'дь-'-Ь' — "1-' способов выбора многочлена О(Х), каждому из которых соответствует необнаруживаемая комбинация ошибок.
Интересующее нас отношение в этом случае равно о (" м. Ч. т. д. Теорема 8.6, из которой можно вывести несколько до некотоРой степени удивительных следствий, утверждает, в частности, что независимо от длины используемого кода и уровня шумов в канале вероятность необнаружения ошибки пропорциональна д ~"-">.
Другими словами, величина Р, определяется главным образом числом проверочных символов. Таким образом, в случае практического использования двоичного кода лишь в очень редких ситуациях потребуется более 30 проверочных символов, а обычно бывает достаточно половины этого числа проверочных символов. В некоторых случаях способность обнаруживать ошибки может сочетаться с другими полезными свойствами специфических кодов.
Например, можно построить БЧХ-код с произвольным кодовым расстоянием 4 который будет обнаруживать любую комбинацию из Й вЂ” 1 или меньшего числа ошибок илн любой пакет ошибок длины и — й или меньше. Может быть построен код, исправляющий любой одиночный пакет ошибок длины Ь, который обнаруживает любую комбинацию из двух пакетов ошибок длины Ь или меньше или любой одиночный пакет ошибок длины и — А или меньше. Примеры. В равд. 8.4 было показано, что двоичный код Хэмминга с кодовым расстоянием, равным 4, можно рассматривать как циклический код. Положим а = 2ш — 1 = 1023. Тогда п — й = = 10+1 = 11. Для кодирования или обнаружения ошибок с помощью этого кода требуется регистр сдвига, содержащий 11 ячеек. Код может обнаруживать любую комбинацию из трех нли меньшего числа ошибок или любой одиночный пакет ошибок длины 11 или меньше. В гл.
9 показано, что можно построить двоичный БЧХ-код с кодовым расстоянием, равным 6, и и = 1023. Для него требуется 21 проверочный символ, и, следовательно, для кодирования и обнаружения ошибок необходим регистр сдвига, содержащий 21 ячейку. Код может обнаруживать любую комбинацию из пяти или меньшего числа ошибок нли любой одиночный пакет ошибок длины 21 илн меньше н подавляющее большинство (99,999957а) всех других комбинаций ошибок.
8.9. Некоторые простые методы исправления ошибок для коротких циклических кодов В этом разделе рассмотрено несколько методов декодирования для циклических кодов. Эти методы пригодны для циклических кодов, исправляющих пакеты ошибок, и для коротких циклических кодов, исправляющих случайные комбинации ошибок. Наиболее известные методы декодирования для длинных кодов, исправляющих случайные комбинации ошибок, а именно методы декодиро" ванна для БЧХ-кодов и мажоритарно-декодируемых кодов, приводятся в следующих главах. Процесс определения кодового слова линейного кода по полученному набору длины и, т. е. декодирование, обычно осуществляется в два этапа.
Во-первых, декодером вычисляется синдром полученного слова. Затем по синдрому определяется образующий смежного класса, который вычитается из полученного слова. Первый этап этого процесса исправления ошибок для случая циклических кодов очень прост„второй — обычно значительно труднее. Синдром, соответствующий набору длины и в линейном коде, представляет собой просто набор длины и — й: з =чНт. (8.20) Для циклического кода вычисление этого набора может быть осуществлено путем деления полученного многочлена на д(Х), поскольку 1чя строка матрицы Нт представляет собой вектор, составленный из коэффициентов остатка, получающегося при делении Х"-' — ~ на у(Х). (См. равд.
8.7.) Операция деления может быть довольно просто осуществлена посредством схемы, изображенной на фиг. 7.6, После того как полученныи набор длины и поступит в регистр, содержимое ячеек регистра совпадет с синдромом. В дальнейшем регистр сдвига с обратной связью, изображенный на фиг. 7.6, связи в котором соответствуют многочлену у(Х), будем называть генератором синдрома для многочлеиа д(Х).
Определение комбинации ошибок по синдрому значительно упрощается благодаря следующей теореме: Теорема 8.7. Пусть через я(Х) обозначен синдром набора г(Х) длины и. Синдром циклического сдвига набора г(Х), т. е. набора Хг(Х), получается в результате одного сдвига генератора синдрома для многочлена у(Х), в котором первоначально содержится я(Х). Доказательство.
Синдром я(Х) может быть получен в виде я(Х) =г(Х) — д(Х) о,(Х), (8.21) где у,,(Х) — частное от деления многочлеиа г(Х) на у(Х), Синдром набора Хг(Х), который обозначим через 1(Х), аналогичным образом представляется в виде 1 (Х) = Хг (Х) — д (К) о, (Х). Умножая равенство (8.21) на Х и вычитая из результата 1(Х), получаем Хя (Х) — 1 (Х) = — д (Х) [Хд,(Х) — д, (Х)). (8.22) Далее следует рассмотреть два случая. Если степень я(Х) меньше чем и — й — 1, то степень Хя(Х) — 1(Х) меньше степени 0(Х), по этому Хя(Х) — !(Х) = О. Таким образом, 1(Х) совпадает с результатом сдвига я(Х) на один разряд вправо„С другой стороны, если степень я(Х) равна л — л — 1, то степень Хя(Х) — !(Х) равна степени 8'(Х), поэтому степень Ха,(Х) — д,(Х) должна быть равна О, т.
е. это должен быть элемент из 6Е(д). Итак, в этом случае ! (Х) = Хя (Х) — ап (Х), где а — некоторый элемент из 6Е(д). Но поскольку многочлен д(Х) является нормированным многочленом, то коэффициент при Х" — "-' в многочлеие я(Х) должен быть равен а. Таким образом, в результате одного сдвига многочлеиа я(Х) в 'генераторе синдрома для д(Х) происходит вычитание ад(Х) из сдвинутого синдрома, которое и дает 1(Х). Ч.
т. д. Это доказательство можно легко распространить на тот случай, когда в качестве синдрома берется произведение Х" — ья(Х), или, более того, произведение миогочлена я(Х), определяемого соотношением (8.20), на некоторый миогочлен. Таким образом, синдром может быть вычислен также при помощи схемы, изображенной па фиг. 8.2, или даже при помощи схемы для укороченных циклических кодов, изображенной на фиг. 8.7. При этом теорема остается по-прежнему справедливой. Типичный декодер для циклических кодов, способный исправить комбинацию ошибок е(Х), может исправить также все комбинации ошибок вида Х'е(Х), где 1(! = и — !.
Кроме того, если может быть исправлена комбинация ошибок г(Х), то (см. равд. 3.5) обычно также могут быть исправлены все ее потомки. При этих условиях в теореме 8.7 по существу утверждается, что если декодером может быть правильно восстановлен первый символ слова для всех исправляемых комбинаций ошибок, то при помогли той же самой схемы можно декодировать это слово целиком. Этот результат позволяет значительно упростить оборудование для декодирования и используется во всех известных процедурах декодирования для циклических кодов. На основании только что рассмотренной теоремы разработан декодер Меггита для циклических кодов (фиг. 8.5).
Генератор синдрома, используемый в этом декодере, несколько отличается от генератора, изображенного на фиг. 7.6, тем, что в нем производится умножение синдрома на Х" — х. (См. фиг. 8.2.) Таким образом, если на вход поступает многочлен г(Х), то в ячейках регистра содержится не многочлеи я'(Х) — синдром для г(Х), а много- член я(Х) = Х"-"я'(Х) по модулю й(Х). Декодер Меггита действует следующим образом: !.
Предположим, что для некоторых, а возможно, и для всех смежных классов образующий выбран. Обычно этот выбор произ- Фиг. 8Л. декодер Меггите дви циклических кодов. слало водится на основе статистики ошибок в канале с тем, чтобы образующий смехаюго класса представлял собой наиболее правдоподобную комбинацию ошибок в этом смежном классе. Предположим также, что для выбранного набора образующих смежных классов каждый циклический сдвиг образующего является образующим смежного класса и каждый потомок образующего также является обрааующим смежного класса. (См.
Равд. 3.5. Декодер Меггита основан на одной из форм поэтапного декодирования.) 2. Полученное слово поступает в буферное устройство и одновременно в генератор синдрома. (Ниже предполагается, что буферное устройство состоит нз и ячеек. Однако, поскольку после декодирования интерес представляют только информационные символы, то достаточно иметь только й ячеек.) 3. Между з(Х), содержимым генератора синдрома, и образующим смежного класса, который следует вычесть из г(Х) для того, чтобы устранить ошибку, имеется взаимно однозначное соответствие. На выходе комбинационной логической схемы должен появиться элемент основного поля — а тогда и только тогда, когда э(Х) соответствует комбинации ошибок с огпибкой, равной а в =имволе высшего разряда, т.
е. в символе, который считывается из буферного устройства. Таким образом, если выход логической "хемы отличен от нуля, то следующий символ, поступающий из буферного устройства, подлежит исправлению. Это осуществляется путем считывания символа из буферного устройства и прибавлении к нему выхода логической схемы. 4. В момент считывания символа из буферного устройства пРоисходит сдвиг генератора синдрома. Если первый символ, по.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
