Скляр Б. Цифровая связь (2003) (1151859), страница 81
Текст из файла (страница 81)
4. Полученный исправленный вектор, или кодовое слово, определяется как () = г+ е,. Можно сказать, что в результате вычитания определенных ошибок мы восстановили верное кодовое слово. (Замечание! в арифметических операциях по модулю 2 операция вычитания равносильна операции сложения.) 6.4.8.3. Локализация модели ошибки оааааа иаюа оиаса юг с!а сосаас асс!а! ссааи ааасс! ооооог !юга! ос!асс го! !с г гогооо асс гоа г гаага ааоиа ааааса сюсса ассаао Юссаа югаи агсссс исаа! ааасас ааасаа аасааа асаааа !ааааа сюааа аисю саго!а !асса! шсаас иоси оооо« !исаа асааю саас са саааас аююс с иаи асс с!с саасаа ааюса !ссссо сиаас ооссас саоасс асаис а!асса июю аассю оасаас ссссас а!сои саоссг асааас юаюс васа!с с!с!и с!сава оассаа сагюса асаио Рис б.11.
Пример иормалыюй магирииы длл кода (6, 3) Определим синдром, соответствующий каждой последовательности исправимых ошибок, вычислив е,П для каждого образующего элемента. 1 0 0 0 1 0 0 0 ! 1 1 0 Я=е г 0 1 1 1 О 1 Результаты приводятся в табл. 6.2. Поскольку все синдромы в таблице различны, декодер может определить модель ошибки е, которой соответствует каждый синдром. Возвращаясь к примеру из раздела 6.4.3, мы составляем матрицу из 2' = шестидесяти четырех б-кортежей, как это показано на рис.
6.!1. Правильные кодовые слова — это восемь векторов в первой строке, а иснравимые модели ошибки — это семь ненулевых образующих элементов классов смежности в первом столбце. Заметим, что все однобитовыс модели ошибки являются исправимыми. Отметим также, что после того, как исчерпываются все однобитовые модели ошибки, еще остаются некоторые возможности для исправления ошибок, поскольку учтены еше не все шестьдесят четыре 6-кортежа. Имеется один образующий элемент класса смежности, с которым ничего не сопоставлено; а значит, остается возможность исправления еще одной модели ошибки. Эту модель ошибки (один из н-кортежей в оставшемся образующем элементе класса смежности) можно выбрать произвольным образом.
На рис. 6.! 1 эта последняя исправимая модель ошибки выбрана равной комбинации с двумя ошибочными битами 01000!. Декодирование будет правильным тогда и только тогда, когда модель ошибки, введенная каналом, будет одним из образующих элементов классов смежности. Таблица 6.2. Таблица соответствия синдромов Модель ошибки Синдром 6.4.8.4. Пример исправления ошибки Как говорилось в разделе 6.4.8.2, мы принимаем вектор г и рассчитываем его синдром с помощью выражения Я = гН'. Затем, используя таблицу соответствия синдромов (табл.
6.2), составленную в предыдущем разделе, находим соответствующузо модель ошибки, которая является оценкой ошибки (далее будем обозначать ее через е ). Затем декодер прибавляет е к г и оценивает переданное кодовое слово () . Ю = г + е = (1) + е) + е = %) + (е + е) (6.40) Если правильно вычислили ошибку: е = е, тогда оценка () совпадает с переданным ко- довым словом 1). С другой стороны, если оценка ошибки неверна, декодер неверно оп- ределит переданное кодовое слово и мы получим необнаружимую ошибку декадизаааиия.
Прнамр 6.4. Исправление ошибок Пусть передано кодовое слово 1) = 101110 из примера в разделе 6.4.3 н принят вектор г= 001110. Нужно показать, как декодер, используя таблицу соответствия синдромов (табл 6 2), может исправить ошибку. Решение Рассчитывается синдром г. Я=(001 1 10] Н =(100] С помощью табл, 6.2 оценивается модель ошибки, соответствующая приведенному выше синдрому. с=1 0 0 0 О 0 Исправленный вектор равен следующему; 0 0 1 1 1 0+1 0 0 0 0 0=. 1 0 ! 1 1 0 Поскольку оцененная модель ошибки в этом поимере совпадает с действительной моделью ошибки, процедура исправления ошибки дает !) = 1).
Можно видеть, что процесс декодирования искаженного кодового слова путем предварительного обнаружения н последующего исправления ошибки можно сравнить с аналогичной 6 4 Лннлйныл блочные колы 000000 00000! 0000!О 000!00 00!000 О!0000 !00000 01000! 000 1О! О!! 11О 00! О!О !00 !!! мелицинской процедурой. Пациент (потенциально искаженный вектор) приходит в медицинское учреждение (декодер), Врач проводит серию тестов (умиожение иа Нт), побы определить симптомы болезни (синаром).
Допустим, врач нашел характерные пятна на рентгенограмме пациента. Опытный врач может непосредственно установить связь между симптомом и болезнью (моделью ошибки). Начинающий врач может обратиться к медицинскому справочнику (табл, 6.2) для определения соответствия между симптомом (синдромом) и болезнью (моделью ошибки).
Последний шаг заключается в назначении соответствуюшето лечения, которое устранит болезнь (ураанеиие (6 40)). Продолжая аналогию двоичных кодов и медицины, можно сказать, что уравнение (6.40) — это несколько необычный способ лечения.
Пациент излечивается в результате повторного заболевания той же болезнью. 6.4.9. Реализация декодера Б=гнт 1 0 0 0 1 0 0 0 1 1 1 О 0 1 1 0 1 Я=(Г! Г2 Гз Гб Г5 Гб! 55=Г!+Г4+Гб 52 52+ Г4+ Г5 55 ГЗ ! Г5 ! Гб Мы используем эти выражения для синдромов при связывании схемы на рис. 6.1 2. Логический элемент "исключающее ИЛИ" — это и есть реализация той самой операции сложения (или вычитания) по модулю 2, поэтому он обозначен тем же символом "+". Маленький кружок в конце каждой линии, входящей в элемент И, означает операцию логического дополнения сигнала. Искаженный сигнал подастся на декодер одновременно в верхней части схемы, где происходит вычисление синдрома, и в нижней, где синдром преобразуется в соответствующую модель ошибки. Ошибка устраняется путем повторного добавления ее к принятому вектору, что дает в итоге исправленное кодовое слово.
Заметим, что с методической точки зрения рис. 6.12 составлен так, чтобы выделить алгебраические этапы декодирования — вычисление синдрома и модели ошибки, а также выдачу исправленных выходных данных. В реальной ситуации код (л, А) обычно выбирается систематическим. Г и 5Г «Г ГГ 4 . 4нГт4.1 Если код короткий, например рассмотренный ранее код (6, 3), декодер может быть реализован в виде довольно простой схемы. Рассмотрим шаги, которые дояжны быть предприняты декодером: (1) вычислить синдром, (2) локализовать модель ошибки и (3) осуществить сложение по модулю 2 модели ошибки и принятого вектора (что приводит к устранению ошибки).
В примере 6.4, имея искаженный вектор, мы покажем, как с помощью последовательности этих шагов можно получить исправленное кодовое слово. Сейчас мы рассмотрим схему, показанную на рис. 6.12, где реализовань! логические элементы исключающего ИЛИ и И, которые позволяют получить тот же результат для любой модели с одним ошибочным битом в коде (6, 3). Из табл.
6.2 и уравнения (6.39) можно записать все разряды синдрома через разряды принятых кодовых слов: Принппкй вектор е Логичеокие влемвнты "исключающее ИЛИ Синдром В Лотичеокне элементы"И Ощнбочная комбинация е Принятый вектор е Иоправленный результат Ц и, из из щ из ив Рис. 6.!2 Схема реализации декодера длл кода 1'6, 3) Декодеру не нужно выдавать полное кодовое слово; на выходе у него должны быть только биты данных. Поэтому схема на рис.
6.12 упрощается за счет удаления заштрихованных элементов. Для более длинных кодов такая реализация намного сложнее; более предпочтительной методикой декодирования является последовательная схема, а не рассмотренный здесь параллельный метод )4). Важно также подчеркнуть, что схема на рис. 6.12 позволяет определять и исправлять только модели кода 16, 3) с одним ошибочным битом. Исправление моделей с двумя ошибочными битами потребует дополнительной схемы.
6.4.9.1. Векторные обозначения Выше кодовые слова, модели ошибок, принятые векторы и синдромы обозначались как векторы 1), е, г и Я. Для упрощения записи индексы, сопутствующие конкретному вектору, в основном, опускались. Хотя, если быть точным, каждый из векторов )), е, г и $ должен записываться в следующем виде: х,= (хнк,, ...,хп ... ) Рассмотрим диапазон индексов 7' и 1 в контексте кода (6, 3), приведенного в табл. 6.1.
Для кодового слова 1)з индекс ) = 1, ..., 2" показывает, что имеется 2' = 8 отдельных кодовых слов, а индекс т'= 1, ..., л демонстрирует, что каждое кодовое слово составлено из а =6 бит. Для исправимой модели ошибки е, индекс 7'= 1, ..., 2" " означает, что имеется 2'м8 образующих элементов классов смежности (7 ненулевых исправимых моделей ошибки), а индекс 1= 1, ..., л указывает, что каждая модель ошибки составлена из л = 6 бит. Для принятого вектора г, индексу'= 1...„2" показывает, что имеется 2 = 64 л-кортежей, прием которых возможен„а индекс / = 1, ..., л указывает, что каж- 6 дый принятый л-кортеж состоит из л = 6 бит.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
