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