Скляр Б. Цифровая связь (2003) (1151859), страница 80
Текст из файла (страница 80)
Заметим, что при использовании этого систематического генератора процесс кодирования еще больше упрощается, поскольку нет необходимости хранить ту часть массива, где находится единичная матрица. Объединяя выражения (6.26) и (6.27), можно представить каждое кодовое слово в следующем виде: рц р„" рцл,> 10" 0 Рг> Ргг "' Рг»и-»> и»,иг,...,ил =[т>,тг,...,т,1х р„р„- р,<„„> 0 0 .- где Ц = ит»рь +тгрь +" +т»рь Лла» =1 ." (л к) для» = (л — »т + 1), ..., л Для данного /с-кортежа сообщения щ = и»ь тг, ..., т„ и 1-кортежа кодовых векторов и! иг и» систематический кодовый вектор можно записать в следующем виде: Р> Р2 ° Рл - » т» т2 "'т» биты иетиоети биты еооби»еаия (6.28) где Р» =»л»рп+т>Рг»+ ...
+и»»рн Р2 ти>Р»2 б»игра+,, +т»р»2 Рл-» =и»>ра»>+ тгрл„»>+ ... +т»Р» „ Систематические кодовые слова иногда записываются так, чтобы биты сообщения занимали левую часть кодового слова, а биты четности — правую. Такая перестановка (6.29) 6.4. Линейные блочные коды 359 Систематический линейный блочный код (бубгещаг!с Ипеаг Ыосх со»)е) (и, /с) — это такое отображение 1-мерного вектора сообщения в л-мерное кодовое слово, в котором часть генерируемой последовательности совмещается с 1 символами сообщения. Остальные (л — 1) бит — это биты четности. Матрица генератора систематического линейного блочного кода имеет следующий вид; не влияет на свойства кода, связанные с процедурами обнаружения и исправления ошибок, поэтому далее рассматриваться не будет.
Для кода (6, 3), рассмотренного в разделе 6.4.3, кодовое слово выглядит следующим образом: )! 1 01 001 () = [ог!,тз,тз] 0 1 1.:0 1 0 1 0 1:,0 О 1 (6.30) (6.31) =т!+тз, т! '! тз, т~ +!пз, т!, тз, т! и1 и, и, и, и, и„ 6.4.6. Проверочная матрица Определим матрицу Н, именуемую ироверочной, которая позволит нам декодировать полученные вектора.
Для каждой матрицы (йх и) генератора С существует матрица Н размером (и — !г) х и, такая, что строки матрицы С ортогональны к строкам матрицы Н. Иными словами, СН =О, где Н" — трангпонированная матрица Н, а 0 — нулевая матрица размерностью хх(п — 1). Н' — это матрица размером !!х(п-к), строки которой являются столбцами матрицы Н, а столбцы — строками матрицы Н. Чтобы матрица Н удовлетворяла требованиям ортогональности систематического кода, ее компоненты записываются в следующем виде: рг! (6.33) Следовательно, матрица Н имеет следующий вид: (6.33,а) 1 О ...
0 0 1 ... 0 0 0 ... ! (6.33,6) Р! ! Рл " Р!.м-г! Рн Рн " Рь!.-и Рн Рн " Рь! -и Глава 6. Канальное кодирование:часть 1 Выражение(6.3!) позволяет получить некоторое представление о структуре линейных блочных кодов. Видно, что избыточные биты имеют разное происхождение. Первый бит четности является суммой первого и третьего битов сообщения; второй бит четности — это сумма первого и второго битов сообщения; а третий бит четности — сумма второго и третьего битов сообщения. Интуитивно понятно, что, по сравнению с контролем четности методом дублирования разряда или с помощью одного бита четности, описанная структура может предоставлять более широкие возможности обнаружения и исправления ошибок. Нетрудно убедиться, что произведение ()Нг любого кодового слова (), генерируемого с помощью матриц С и Н', дает следующее: ()Н =Р1+Р1 Рз+Ръ "'Р -г+Р -«=О т где биты четности рь рь ...,р„» определены в уравнении (6.29).
Таким образом, поскольку лроверочиая матрица Н создана так, чтобы удовлетворять условиям ортогональности, она позволяет проверять принятые векторы на предмет нх принадлежности заданному набору кодовых слов. (1 будет кодовым словом, генерируемым матрицсй С, тогда и только тогда, когда ()Нг= О. 6.4.7. Контроль с помощью синдромов г =(1+е. (6.34) Здесь е =еь е,, ..., е„— вектор ошибки или модель ошибки, внесенная каналом. Всего в пространстве из 2" л-кортежей существует 2" — 1 возможных ненулевых моделях ошибки. Синдром сигнала г определяется следующим образом: Б=гН .
(6.35) Синдром — это результат проверки четности, выполняемой над сигналом г лля определения его принадлежности заданному набору кодовых слов. При положительном результате проверки синдром $ равен О. Если г содержит ошибки, которые можно исправить, то синдром (как и симптом болезни) имеет определенное ненулевое значение, что позволяет отметить конкретную модель ошибки. Декодер, в зависимости от того, производит ли он прямое исправление ошибок или использует запрос АКС), участвует в локализации и исправлении ошибки (прямое исправление ошибок) или посылает запрос на повторную передачу (АЩ). Используя уравнения (6.34) и (6.35), мы можем представить синдром г в следующем виде: Я = (()же)Н ПНг+еНг (6.36) Но для всех элементов набора кодовых слов 11Н = О. Поэтому Я = еН . т (6.37) Из сказанного выше очевидно, что контроль с помощью синдромов, проведенный над искаженным вектором кода или наа моделью ошибки, вызвавшей его появление, даст один и тот же синдром.
Важной особенностью линейных блочных кодов (весьма важной в процессе декодирования) является взаимно однозначное соответствие между синдромом и поправимой моделью ошибки. Интересно также отметить два необходимых свойства проверочной матрицы. 1. В матрице Н не может быть столбца, состоящего из одних нулей, иначе ошибка в соответствующей позиции кодового слова не отразится в си~щроме и не будет обнаружена. Пусть г = гь гь ..., г„— принятый вектор (один из 2' л-кортежей), полученный после передачи (1 = иь иь ..., и„(один из 2" я-кортежей). Тогда г можно представить в сле- дующем виде: 2.
Все столбцы матрицы Н должны быль различными. Если в матрице Н найдется два одинаковых столбца, ошибки в соответствующих позициях кодового слова будут неразличимы. Пример блй Контроль с помощью синдромов Пусть передано кодовое слово 1) = 1 О 1 1 1 О из примера в разделе б.л 3 и принят вектор г = 00 1 1 10, т.е. крайний левый бит принят с ошибкой. Нужно найти вектор синдрома Я = гН" и показать, что он равен еН". Решение Я = гН т 100 0 1 0 !О 0 1 1 1 О] 001 ! 1 0 0 1 ! 1 0 1 = !1, !+1, !+1]=!! 0 !](синдромискшкенноговекторакода) Далее проверим, что синдром искаженного вектора кода равен синдрому модели ошибки, которая вызвала зту ошибку Я=еН = [100 000! Н =!! 00) (синдром модели ошибки) 6.4.8.
Исправление ошибок Итак, мы обнаружили отдельную ошибку и показали, что контроль с помощью синдромов, выполняемый как на искаженном кодовом слове, так и на соответствующей модели ошибки, дает один и тот же синдром. Этот момент является ключевым, поскольку мы имеем возможность не только определить ошибку, но и (поскольку существует взаимно однозначное соответствие между исправимой моделью ошибки и синдромом) исправить подобные модели ошибки.
Давайте так расположим 2" »-кортежей, которые представляют собой возможныс принимаемые векторы, в так называемой нормальной матрице, чтобы первый ряд содержал все кодовые слова, начиная с кодового слова с одними нулями, а первый столбец — все исправимые модели ошибки. Напомним, что основным свойством линейного кода является то, что в набор кодовых слов включен вектор, состоящий из одних нулей.
Каждая строка сформированной матрицы, именуемая классом смене»осели, состоит из модели ошибки в первом столбце, называемой образующим элементом класса смене»ости, за которой следуют кодовые слова, подвергающиеся воздействию этой модели ошибки. Нормальная матрица для кода (», А) имеет следующий вид: ~г' О +е ()г "ез (), +ег () +ез ьзг+ег ~г+ез ег е ()г +е " (), +е "- 1)г, +е (6.38) г+ег" ' (), +ег. " Е,и+е, 6.4.8.1.
Синдром класса смежности Если е, является образующим элементом класса смежности или моделью ошибки /- го класса смежности, то вектор Ц+ е, является л-кортежем в этом классе смежности. Синдром этого л-кортежа можно записать в следующем виде: ч=(11 + в)Нт=()Нт+еНт Поскольку Ц вЂ” это вектор кода и ЦНт = б, то, как и в уравнении (6.37), мы можем записать следующее: Я = (Ц + е,)Н = е,Н . (6.39) Вообше, название класс смежности (или самиолсество) — это сокращение от "множество чисел, имеющих совместные свойства".
Что же все-таки обшего между членами каждой данной строки (класса смежности)? Из уравнения (6.39) видно, что каждый член класса смежности имеет один и лзолз лсе синдром. Синдром каждого класса смежности отличается от синдромов других классов смежности; именно этот синдром используется для определения модели ошибки. 6.4.8.2. Декодирование с исправлением ошибок Процелура декодирования с исправлением ошибок состоит из следующих этапов. 1. С помошью уравнения Я = гН вычисляется синдром г. 2. Определяются образующие элементы класса смежности (модели ошибки) е,, синдром которых равен гНт. 883 Отметим, что кодовое слово Ц (кодовзе слово со всеми нулями) играет две роли. Оно является кодовым словом, а также может рассматриваться как модель ошибки е, — комбинация, означаюшая отсутствие ошибки, так что г= 11. Матрица содержит все 2" лкортежей, имеющихся в пространстве 1'„.
Каждый л-кортеж упомянут лкмько адил роз, причем ни один нс пропущен и не продублирован. Каждый класс смежности содержит 2' л-кортежей. Следовательно, всего классов смежности будет (2т2') = 2" '. Алгоритм декодирования предусматривает замену искаженного вектора (любого лкортежа, за исключением указанного в первой строке) правильным кодовым словом, указанным вверху столбца, содержашего искаженный вектор.
Предположим, что кодовое слово Ц (1 = 1, ..., 2') передано по каналу с помехами, в результате чего принят (искаженный) вектор Ц + ет Если соианная каналом модель ошибки е, является образующим элементом класса смежности с индексом у = 1..., 2" ', принятый вектор будет правильно декодирован в переданное кодовое слово Ц Если модель ошибки не является образуюшим элементом класса, то декодирование даст ошибочный результат. 3. Полагается, что модели ошибки вызываются искажениями в канале.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
