Скляр Б. Цифровая связь (2003) (1151859), страница 107
Текст из файла (страница 107)
Мы выразим полиномиальный генератор через 2г = л — )г = 4 корня следующим образом: 8(х) = (Х вЂ” аХх — а') (х — а') (х — а") = (Хб (а+ аб)Х+ аб)(Хг (аб+ сбб)Х+ сб7) = (Х2 гхбХ + аЗ)(Х2 бХ 0) Хб ( б б)ХЗ ( „3 $0 0)Х2 ( 4 9)Х б = хб - абхб + абхб — а'х + аб . Поменяв порядок расположения членов полинома на обратный и заменив знаки "минус" на "плюс", так как над двоичным полем +! =-1, генератор 8(Х) можно будет представить следующим образом: 8(Х) = а + а Х+ а Х + а Х + Хб.
(8.22) 8.1.5.1. Кодирование в систематической форме Х" ~ш(Х) = б((Х)8(Х) + р(Х). (8.23) Здесь о(Х) и р(Х) — это частное и остаток от полиномиального деления. Как и в случае двоичного кодирования, остаток будет четным. Уравнение (8.23) можно переписать следующим образом: р(Х) = Х" бш(Х) по модулю 8(Х). (8.24) 473 8.1. Коды Рида-Соломона Так как код Рида-Соломона является циклическим, кодирование в систематической форме аналогично процедуре двоичного кодирования, разработанной в разделе 6.7.3. Мы можем осуществить сдвиг полинома сообщения ш(х) в крайние правые )б разряды регистра кодового слова и произвести последующее прибавление полинома четности р(Х) в крайние левые и — А разряды. Поэтому мы умножаем ш(Х) на Л проделав алгебраическую операцию таким образом, что ш(Х) оказывается сдвинутым вправо на и — )г позиций.
В главе 6 это показано в уравнении (6.61) на примере двоичного кодирования. Далее мы делим Л 'гп(Х) на полиномиальный генератор 8(Х), что можно записать следующим образом: кодового слова ()(Х), показанный в уравнении (6.64), образом: ()(Х)=р(Х)+Х" "т(Х). (8.25) подразумеваемые уравнениями (8.24) и (8.25), закодиролов 010 11О 111 а2 аз 422 на (7, 3), генератор которого определяется уравнением (8.22). вверх) полипом сообшения сб'+сбзХ+азХ' на Л" "=Х', что 2 делим такой сдвинутый вверх лелином сообшения на полиномиальный генератор из уравнения (8.22), аз+ сб'Х+ аОХЗ+ а'Хз+ Х'. Пааиномиальное деление недвоичных коэффициентов — это еше более утомительная процедура„чем ее двоичный аналог (см.
пример 6.9), поскольку операции сложения (вычитания) и умножения (деления) выполняются согласно табл. 8.2 и 8.3. Мы оставим читателю в качестве самостоятельного упражнения проверку того, что полиномиальное деление ласт в результате следуюший полиномиальный остаток (полипом четности): р(Х) с40 + 422Х + 4 24Х2 + пбХз Затем, из уравнения (8.25), полином кодового слова можно записать следуюшим образом: ()(Х) О 2Х 4Х2 ОХЗ 3Х4 ЗХЗ Злб 8. З.б.2. Систематическое кодирование с помощью (л — й)-разрядного регистра сдвига Как показано на рис.
8.9, кодирование последовательности из 3 символов в систематической форме на основе кода Рида-Соломона (7, 3), определяемого генератором 8(Х) из уравнения (8.22), требует реализации регистра (.Рбй. Нетрудно убедиться, что элементы умножителя на рис. 8.9, взятые справа налево, соответствуют коэффициентам полинома в уравнении (8.22). Этот процесс кодирования является недвоичным аналогом циклического кодирования, которое описывалось в разделе 6.7.5.
Здесь, в соответствии с уравнением (8.20), ненулевые кодовые слова образованы 2 — 1=7 символами, и каждый символ состоит из л2 = 3 бит. 3 длея ДОЕЕТЕЛЬНООТЬ ОЛОЕ ОООООЗЕЛЕЕ Переключатель 2 а' аЗ аб Рис В.9. Кодер ЕКБИ длл кодо (7, 3) 474 Глава В. Канальное кодирование: часть 3 1. Переключатель 1 в течение первых Ь тактовых импульсов закрыт, для того чтобы подавать символы сообщения в (л — й)-разрядный регистр сдвига. 2. В течение первых к тактовых импульсов переключатель 2 находится в нижнем положении, что обеспечивает одновременную передачу всех символов сообщения непосредственно на регистр выхода (на рис.
8.9 не показан). 3. После передачи lг-го символа на регистр выхода, переключатель 1 открывается, а переключатель 2 переходит в верхнее положение. 4. Остальные (л — А) тактовых импульсов очищают контрольные символы, содержащиеся в регистре, подавая их на регистр выхода. 5. Общее число тактовых импульсов равно а, и содержимое регистра выхода является полиномом кодового слова р(Х)+Х "т(Х), где р(Х) представляет собой кодовые символы, а т(Х) — символы сообщения в полиномиальной форме. Для проверки возьмем ту же последовательность символов, что и в разделе 8.1.5.1. 010 110 111 аз аз сс5 Здесь крайний правый символ является самым первым и крайний правый бит также является самым первым. Последовательность действий в течение первых й = 3 сдвигов в цепи кодирования на рис.
8.9 будет иметь следующий вид. ОЧЕРЕДЬ ВВОДА СОДЕРЖИМОЕ РЕГИСТРА О О О О ОБРАТНАЯСВЯЗЬ ТАКТ О 1 2 3 а' аз а' аз аз а' О аз аз а4 а' аз ао аз а4 а' Как можно видеть, после третьего такта регистр содержит 4 контрольных символа, а', а', а' и а'. Затем переключатель 1 переходит в верхнее положение, и контрольные символы, содержащиеся в регистре, подаются на выход.
Поэтому выходное кодовое слово, записанное в полиномиальной форме, можно прелставить в следующем виде: 8.1. Коды Рида-Соломона 4?б Следует отметить сходство между рис. 8.9, 6.18 и 6,19. Во всех трех случаях количество разрядов в регистре равно л — зг. Рисунки в главе 6 отображают пример двоичного кодирования, где каждый разряд содержит 1 бит. В данной главе приведен пример недвоичного кодирования, так что каждый разряд регистра сдвига, изображенного на рис.
8.9, содержит 3-битовый символ. На рис. 6.18 коэффициенты, обозначенные Яо Вм ..., являются двоичными. Поэтому они принимают одно из значений 0 или 1, просто указывая на наличие или отсутствие связи в (.ГЗВ. На рис. 8.9 каждый коэффициент является 3-битовым„так что они могут принимать одно из 8 значений. Недвоичные операции, осуществляемые кодером, показанным на рис. 8.9, создают кодовые слова в систематической форме, так же как и в двоичном случае. Эти операции определяются следующими шагами.
6 Ц(Х) = ~> и„Х", 4=0 О 2Х+ 4~ 2 ОХЗ !Х4+ 3, 5+ 5ХО (8.26) = (1ОО) + (ООЦХ+ (О(ЦХ'+(ГОЦХ'+ (О18)Х'+ (ИО)Х'+ (11ЦХ'. Процесс проверки содержимого регистра во время разных тактов несколько сложнее, чем в случае бинарного кодирования. Здесь сложение и умножение элементов поля должны выполняться согласно табл. 8.2 и 8.3.
Корни полиномиального генератора 8(Х) должны быть и корнями кодового слова, генерируемого 8(Х), поскольку правильное кодовое слово имеет следующий вид: Ц(Х) = 2п(Х)8(Х). (8.27) Следовательно, произвольное кодовое слово, выражаемое через корень генератора 8(Х), должно давать нуль. Представляется интересным, действительно ли полипом кодового слова в уравнении (8.26) дает нуль, когда он выражастся через какой-либо из четырех корней 8(Х). Иными словами, это означает проверку следующего: Ц(и) Ц(о2) Ц(!23) Ц(а4) О Независимо выполнив вычисления для разных корней, получим следующее: Ц(и) =аО+а3+и6+а3+и5+и0+а!! = = а'+ а'+ а'+ а'+ а'+ и' + а4 = ,!+ О+ 6+ 4 = а3 + и3 = О, Ц(и2) =и05-а45-а6+а" +а'5-и!3+а" = = 020+ и'+ а' + и!+ а'+ а'+ а' = =а'+а'+00+а'= =02'+а' =О, ц(а3) = а'+ а'+ а" + а" + ао+ а" + а" = 1,!О+025+ 23+ 21+ 6+ 4+ 2 с!4+!.!О+ .
3+ 2 =а'+а'=О, Ц( 4) О+ 6+ а+ а+ и+ „23+ О 6+ 5+ 4+ 3+ 2+ ! = а'+ а'+ и5+ а' = = а' + а' = О. Эти вычисления показывают, что, как и ожидалось, кодовое слово, выражаемое через любой корень генератора 8(Х), должно давать нуль. 8.1.6. Декодирование Риде-Соломоне В разделе 8.1.5 тестовое сообщение кодируется в систематической форме с помощью кода Рида-Соломона (7„3), что даст в результате полипом кодового слова, описываемый уравнением (8.26). Допустим, что в ходе передачи это кодовое слово подверглось искажению: 2 символа были приняты с ошибкой. (Такое количество ошибок соответ- 476 Глава 8. Канальное кодирование: часть 3 е(Х) = ~ е„Х" . ь=а Пусть двухсимвольная ошибка будет такой, что (8.28) е(Х) = О+ОХ+ОХ'+азХ'+~аХ4+ОХ' еОХ'= (8.29) = (ООО) + (ООО)Х + (ООО)Х + (ОО ПХ + ( Ш)Х + (ООО)Х + (ООО)Х .
Другими словами, контрольный символ искажен 1-битовой ошибкой (представленной как аз), а символ сообшения — 3-битовой ошибкой (представленной как сг). В данном случае принятый полипом поврежденного кодового слова г(Х) представляется в виде суммы полинома переданного кодового слова и полинома модели ошибки, как показано ниже. г(Х) = ЩХ) + е(Х) (8.30) Следуя уравнению (8.30), мы суммируем ЩХ) из уравнения (8.26) и е(Х) из уравнения (8,29) и имеем следуюшее: г(Х) = (100) ч (001)Х+ (011)Х' е (100)Х'.ь (101)Х'+ (110)Х'+ (111)Х'- 0 з» 4Х2 ОХ» 6Х4 3Х5 5Хб (8.31) В данном примере исправления 2-символьной ошибки имеется четыре неизвестных — два относятся к расположению ошибки, а два касаются ошибочных значений.
Отметим важное различие между недвоичным декодированием г(Х), которое мы показали в уравнении (8.31), и двоичным, которое описывалось в главе 6. При двоичном декодировании декодеру нужно знать лишь расположение ошибки. Если известно, где находится ошибка, бит нужно поменять с 1 на 0 или наоборот. Но здесь недвоичные символы требуют, чтобы мы не только узнали расположение ошибки, но и определили правильное значение символа, расположенного на этой позиции. Поскольку в данном примере у нас имеется четыре неизвестных, нам нужно четыре уравнения, чтобы найти их.
8.1.6.1. Вычисление синдрома Вернемся к разделу 6.4.7 и напомним, что синдром — это результат проверки четности, выполняемой над г, чтобы определить, принадлежит ли г набору кодовых слов. Если г является членом набора, то синдром Я имеет значение, равное О. Любое ненулевое значение Я означает наличие ошибок.
Точно так же, как и в двоичном случае, синдром Я состоит из л — /с символов, (5,) (г = 1, ..., и — Ус). Таким образом, для нашего кода (7, 3) имеется по четыре символа в каждом векторе синдрома; их значения можно рассчитать из принятого полинома г(Х). Заметим, как облегчаются вычисления благодаря самой структуре кода, определяемой уравнением (8.27). ЩХ) = го(Х)8(Х) 8.1. Коды Рида-Соломона ствует максимальной способности кода к коррекции ошибок.) При использовании 7- символьного кодового слова модель ошибки можно представить в полиномиальной форме следуюшим образом: 5, =г(Х)~„„, =г(а') 1=1,...,л — Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
