Прокис Дж. - Цифровая связь (1266501), страница 78
Текст из файла (страница 78)
Другими словами, вектор Я имеет нулевые компоненты для тех уравнений проверочных символов, которые выполняются, и ненулевые компоненты для тех уравнений проверочных символов, которые не выполняются. Таким образом, Я содержит образец неудач проверок. Подчеркнем, что синдром Я является характеристикой образцов ошибок, но не переданных кодовых слов. Далее заметим, что имеется 2" возможных образцов ошибок, но только 2" ' синдромных. Следовательно, различные образцы ошибок приводят к одинаковым синдромам.
Предположим, мы сконструируем таблицу декодирования 2" х 2 ', в заголовке которой запишем все 2" возможных кодовых слов, начиная кодовым словом из одних нулей в первом (самом левом) столбце. Это кодовое слово из одних нулей представляет также образец ошибки, состоящий из одних нулей. Мы заполним первый столбец путем записи сначала всех образцов ошибок (е,) с весом 1 (их число равно и+1). Если и с 2' ' „ мы можем затем записать образцы двойных ошибок, затем образцы тройных ошибок и т.д., пока не получим общее 2 ' записей в первом столбце. Таким образом, число строк.
которые можно иметь в таблице, равно 2" ", что равно числу возможных синдромов. Далее мы суммируем каждый образец ошибки из первого столбца с соответствующими кодовыми словами, расположенными в верхней строке таблицы. Так мы заполняем остаток таблицы следукнцим образом С, е, С,+е, Этот код имеет минимальное расстояние Ы . =3, Стандартное расположение дано в табл. (8.1.7).
Заметим, что в этом коде среди 8 лидеров смежных классов один состоит из одних нулей, пять лидеров имеют вес, равный 1 и два имеют вес, равный 2. Хотя имеется много больше образцов двойных ошибок, здесь достаточно двух, чтобы заполнить таблицу. Табл. 8Л.7. Стандартное расположение длн кода (5, 2) Кодовые слова 00000 01011 10101 11110 Они были выбраны так, чтобы соответствующие им синдромы отличались от тех, которые соответствуют одиночным ошибкам. Теперь предположим, что е,.
являются лидером смешанного класса, и что было передано кодовое слово С„. Тогда образец ошибки е, приводит к принимаемому ходовому слову к =С„+е, Синдром равен Я =(С +е,.)Н' =С„Н'+е,Н' =е,Н'. Ясно, что все принимаемые кодовые слова в тех же смежных классах, образованные из твх же е,, имеют одинаковые синдромы, поскольку последние зависит только от образцов сшибки, Далее, каждый смежный класс, образованный различным е, имеет свой синдром. установив эти характеристики нз стандартного расположения, мы можем просто сконструировать синдромную таблицу декодирования, в которой запишем 2 в синдромов и соответствующие 2" ' лидеров смешанных классов, которые представляют образцы сшибок с минимальным весом. Затем„для данного принимаемого кодового вектора Ъ' мы вычисляем синдром Б = 'в'Н' Для вычисленного синдрома Б мы находим соответствующий (наиболее .
правдоподобный) вектор ошибки, скажем е . Этот вектор ошибки суммируется с Ъ. :. чтобы получить декодированное слово С„=УЮе . Пример 8Л.11. Рассмотрим код (5, 2) со стандартным расположением, данным в :, таблице (8.1.7). Синдромы, соответствующие наиболее правдоподобным образцам '::, ошибок, даны в таблице (8.1.8). Теперь предположим, что действительный вектор ошибок " вквнале е = [1 0 1 0 01 Синдром, вычисленный для этой ошибки, равен Я = 1001].
Ошибка, определяемая по -:: втому синдрому из таблицы, равна е=[00001]. Когда е суммируется с Ъ', результат 383 00001 000 10 00100 01000 10000 11000 10010 01010 01001 01111 00011 11011 10011 11001 10100 10111 10001 11101 00101 01101 00111 11111 11100 11010 10110 01110 00110 01100 приведет к ошибке декодирования. Другими словами, код (5, 2) корректирует все одиночные ошибки и только две двойные ошибки, именно [11000~ и (10010]. р Г Г Табл. 8.1.8. Таблица синдромов для кода (5, 2) Синдромное декодирование циклических кодов. Как описано выше, декодирование жестких решений для линейного блокового кода можно выполнить, вычислив сначала синдром Я = УН', затем найдя по таблице синдромов наиболее вероятный образец ошибки е, соответствующий вычисленному синдрому Я, и, наконец, суммируя образец ошибки е с принятым вектором У, чтобы получить в качестве решения наиболее правдоподобное кодовое слово С„.
Когда код циклический, вычисление синдрома можно выполнить с помощью регистра сдвига, подобного тому, который использовался в кодере. Для более подробного обсуждения рассмотрим систематический циклический код и представим принимаемый кодовый вектор Ъ' полиномом У(р). В общем х'= С+е,где С- переданное кодовое слово, а е — вектор ошибки. Таким образом, имеем У(р) = С(р)+ е(р) = Х(рЩр) + е(р) . (8.1.77) Теперь разделим У(р) на порождающий полином 8(р) . Это деление дает 1'(р) ()(р),) Ы (р) " 'аЫ у(р) = аЫ8(р). ~(р)- (8.1.78) Остаток Я(р) — полипом степени, меньшей или равной и — к — 1. Если объединить (8.1.77) и (8.1.78), получим е(р) = (Х(р)+<Яр)фр)+ й(р). (8.1.79) Это соотношение показывает, что остаток А(р), полученный от деления у(р) на 8(р), зависит только от полинома ошибки е(р) и, следовательно, Л(р) — это просто синдром Я(р), связанный с образцом ошибки е.
Таким образом, уЫ = а(р)аЫ+~(р), (8.1.80) где Я(р) — полином синдрома степени меньшей илн равной и- к -1. Если У(р) делится на 8(р) точно (без остатка), тогда Я(р) = О и принятое слово определяет решение декодера: С„=У. Синдром 000 001 010 100 011 101 110 !11 Вектор ошибки 00000 00001 00010 00100 01000 10000 11000 10010 Вмвидпай аиидрам Рнс. 8.1.9. (л-Ф)-каскадный регистр сдннгд для вычисления синдрома Пример ЗЛ.12. Рассмотрим вычисление синдрома для циклического кода Хемминга (7,4) с порождающим полиномом фр)= р'+р+1. Предположим, что принят вектор т'- [10011011. Он подастся на трехкаскадный регистр, показанный на рисунке 8.1.10.
Сдвиг Садгрмимаа рггиатра ооо 1ОО 010 ОШ шо 101 1ОО по Вмиадиай лиидралг Влад 1опоо~ Рнс. 8.1,10. Вычисление синдрома для цнклнческого коде (7„4) с порождаощнм полнномом я1р)=рз+р+1 прн принимаемом векторе к'=11 О О 1 1 О Ц После семи сдвигов содержимое регистров сдвига 110, что соответствуют синдрому 8 = [0111. Этому синдрому соответствует наиболее правдоподобный вектор ошибки е = [0001000~ и, следовательно, С. = ~+е = [10001011.
Информационные символы 1000. Метод справочной таблицы, использующей синдром, практически используется тогда, когда н — гг мало, например, и — И «10. Этот метод не подходит для многих интересных мощных кодов. Например, если н — гг =20, таблица имеет 2'" (примерно 1 миллион) записей. Необходимость хранения большого количества данных и затраты времени, требуемые для обнаружения нужных записей в такой большой таблице, делает метод декодирования со справочной таблицей непрактичным для длинных кодов, имеющих большое число проверочных символов.
25 — 56 З85 Деление ) (р) на порохгдающий полипом 8~р) можно выполнить посредством регистра сдвига, выполняющего деление, как описано ранее. Сначала принимаемый вектор т' передвигается по 1п-1г) -каскадному регистру сдвига, как показано на рис. 8.1.9. Первоначально все ячейки регистра сдвига обнулены, а ключ находится в положении 1. После того как весь принятый н-символьный вектор вошел в регистр, содержимое и — 1г ячеек образует синдром в порядке следования символов, указанном на рис. 8.1.9.
Эти символы поочередно извлекаются из регистра при установке ключа в положение 2. По заданному синдрому от 1н — я)-каскадного регистра сдвига и справочной таблице можно идентифицировать наиболее вероятный вектор ошибки. Для класса циклических кодов и более сложного класса БЧХ кодов были разработаны более эффективные алгоритмы декодирования жестких решений. Описание этих алгоритмов требует дальнейшей разработки вычислительных методов в конечных полях, которые находятся вне нашей области охвата теории кодирования. Достаточно указать, что существует алгоритмы эффекгивного декодирования, что делает возможным реализовать длинные БЧХ коды с большой избыточностью в практике цифровых систем связи.
Интересующего читателя отправляем к книгам Питерсона и Уэлдона (1972), Лина и Костелло (1983), Блейхута (1983), Берлекэмпа (1968) и к сгатье Форин (19б5). Способность обнаружения н исправления ошибок. Из вышеизложенного ясно, что когда синдром содержит одни нули, принимаемое кодовое слово являются одним из 2" возможных к передаче кодовых слов. Поскольку минимальное расстояние между парой кодовых слов равно с(„„„, образец ошибки весом ~(,. может трансформировать один нз этих 2 кодовых слов кода в другое кодовое слово. Если это случается, мы имеем иеоб((ауулсеии3:(о ошибку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
