Читайте также: |
|
= а0 + а6Х + а°Х2.
Корни а(Х) являются обратными числами к положениям ошибок. После того как эти корни найдены, мы знаем расположение ошибок. Вообще, корни а(Х) могут быть одним или несколькими элементами поля. Определим эти корни путем полной проверки полинома а(Х) со всеми элементами поля, как будет показано ниже. Любой элемент X, который дает а(Х) = 0, является корнем, что позволяет нам определить расположение ошибки.
a(a°) = a0 + a6 + a0 = a6 * О a(a') = a2 + a7 + a0 = a2 * 0 a(a2) = a4 + a8 + a0 = a6 * 0 a(a3) = a6 + a9 + a0 = 0 => ОШИБКА
о(а4) = а8 + а10 + а0 = 0 => ОШИБКА а(а5) = а10 + а" + а0 = а2 * О а(а6) = а12 + а12 + а0 = а0 * О Как видно из уравнения (8.39), расположение ошибок является обратной величиной к корням полинома. А значит, о(а3) = 0 означает, что один корень получается при 1/Р/ = а3. Отсюда р( = 1/а3 = а4. Аналогично о(а4) = 0 означает, что другой корень появляется при I/р;- =1/а4 =а3, где (в данном примере) / и /' обозначают 1-ю и 2-ю
ошибки. Поскольку мы имеем дело с 2-символьными ошибками, полином ошибок можно записать следующим образом:
e(X)=ehXJ'+ej2XJi.
Здесь были найдены две ошибки на позициях а3 и а4. Заметим, что индексация номеров расположения ошибок является сугубо произвольной. Итак, в этом примере
мы обозначили величины Р; = аЛ как = aJ' =а3 и р2 = aJl =а4.
8.1.6.3. Значения ошибок
Мы обозначили ошибки е}1, где индекс j обозначает расположение ошибки, а индекс I — 1-ю ошибку. Поскольку каждое значение ошибки связано с конкретным месторасположением, систему обозначений можно упростить, обозначив eJ/ просто как et. Теперь, приготовившись к нахождению значений ошибок е{ и е2, связанных с позициями = а3 и р2 = а4, можно использовать любое из четырех синдромных уравнений. Выразим из уравнения (8.38) 5, и S2.
=г(а) = е1р1 +е2Рг
S2 =г(а2) = ejPf +е2р f Эти уравнения можно переписать в матричной форме следующим образом:
'Pi | Р2‘ | V | 'V | |
.Pi | Pi. | ,е2_ | 52. | |
а3 | а4' | V | а3" | |
Р О* | а8 | -е2_ | а5 |
Чтобы найти значения ошибок ех и е2, нужно определить обратную матрицу для уравнения (8.52).
а
а3а‘-а6а4 |
а4 + а3 |
Теперь мы можем найти из уравнения (8.52) значения ошибок.
V | а2 | а5 | а3' | а5 + а10 | '5 3' а +а | а2 | ||||
/2. | а0 | а4 | а5 | а3 +а9 | 3 2 а +а | а5 |
8.1.6.4. Исправление принятого полинома с помощью найденного полинома ошибок
Из уравнений (8.49) и (8.54) мы находим полином ошибок.
ё(Х) = elXJl + e2Xh =
= а2Х3+а5Хл
Показанный алгоритм восстанавливает принятый полином, выдавая в итоге предполагаемое переданное кодовое слово и, в конечном счете, декодированное сообщение.
U(X) = г(Х) +ё(Х) = U(X) + е(Х) + £(Х) (8.56)
г(Х) = (100) + (001)Х + (011)Х2 + (100)X3 + (101)X4 + (ПО)*5 + (lll)X6 ё(Х) = (ООО) + (000)Х + (000)Х2 + (001)Х3 + (111)Х4 + (000)Х5 + (ООО)*6
й(Х) = (ЮО) + (ooi)x
= а0 + а2Х + а4*2 + а6*3 + а'Х4 + а3*5 + а5*6 (8.57)
Поскольку символы сообщения содержатся в крайних правых к = 3 символах, декодированным будет следующее сообщение:
010 110 111.
aJ
Это сообщение в точности соответствует тому, которое было выбрано для этого примера в разделе 8.1.5. (Для более детального знакомства с кодированием Рида- Соломона обратитесь к работе [6].)
8.2. Коды с чередованием и каскадные коды
В предыдущих главах мы подразумевали, что у канала отсутствует память, поскольку рассматривались коды, которые должны были противостоять случайным независимым ошибкам. Канал с памятью — это такой канал, в котором проявляется взаимная зависимость ухудшений передачи сигнала. Канал, в котором проявляется замирание вследствие многолучевого распространения, когда сигнал поступает на приемник по двум или бсшее путям различной длины, есть примером канала с памятью. Следствием является различная фаза сигналов, и в итоге, суммарный сигнал оказывается искаженным. Таким эффектом обладают каналы мобильной беспроводной связи, так же как ионосферные и тропосферные каналы. (Более подробно о замирании см. главу 15.) В некоторых каналах также имеются коммутационные и другие импульсные помехи (например, телефонные каналы или каналы с создаваемыми импульсными помехами). Все эти ухудшения коррелируют во времени и, в результате, дают статистическую взаимную зависимость успешно переданных символов. Иными словами, искажения вызывают ошибки, имеющие вид пакетов, а не отдельных изолированных ошибок.
Если канал имеет память, то ошибки не являются независимыми, одиночными и случайно распределенными. Большинство блочных и сверточных кодов разрабатывается для борьбы с независимыми случайными ошибками. Влияние канала с памятью на кодированный таким образом сигнал приведет к ухудшению достоверности передачи. Существуют схемы кодирования для каналов с памятью, но наибольшую проблему в этом кодировании представляет расчет точных моделей сильно нестационарных статистик таких каналов. Один подход, при котором требуется знать только объем памяти канала, а не его точное статистическое описание, использует временное разнесение, или чередование битов.
Чередование битов кодированного сообщения перед передачей и обратная операция после приема приводят к рассеиванию пакета ошибок во времени: таким образом, они становятся для декодера случайно распределенными. Поскольку в реальной ситуации память канала уменьшается с временным разделением, идея, лежащая в основе метода чередования битов, заключается в разнесении символов кодовых слов во времени. Получаемые промежутки времени точно так же заполняются символами других кодовых слов. Разнесение символов во времени эффективно превращает канал с памятью в канал без памяти и, следовательно, позволяет использовать коды с коррекцией случайных ошибок в канале с импульсными помехами.
Устройство чередования смешивает кодовые символы в промежутке нескольких длин блоков (для блочных кодов) или нескольких длин кодового ограничения (для сверточных кодов). Требуемый промежуток определяется длительностью пакета. Подробности структуры битового перераспределения должны быть известны приемнику, чтобы иметь возможность выполнить восстановление порядка битов перед декодированием. На рис. 8.10 показан простой пример чередования. На рис. 8.10, а мы можем видеть кодовые слова, которые еще не подвергались описанной операции, от А до G. Каждое кодовое слово состоит из семи кодовых символов. Пусть наш код может исправлять однобитовые ошибки в любой 7-символьной последовательности. Если промежуток памяти канала равен длительности одного кодового слова, такой пакет, длительностью в семь символов, может уничтожить информацию в одном или двух кодовых словах. Тем не менее допустим, что после получения кодированных данных кодовые символы затем перемешиваются, как показано на рис. 8.10, б. Иными словами, каждый кодовый символ каждого кодового слова отделяется от своего соседа на расстояние из семи символьных периодов. Полученный поток затем преобразуется в модулированный сигнал и передается по каналу. Как можно видеть на рис. 8.10, б, последовательные канальные пакеты шума попадают на семь символьных промежутков, влияя на один кодовый символ каждого из семи исходных кодовых слов. Во время приема в потоке вначале восстанавливается исходный порядок битов, так что он становится похож на исходную кодированную последовательность, изображенную на рис. 8.10, а. Затем поток декодируется. Поскольку в каждом кодовом слове возможно исправление одиночной ошибки, импульсная помеха не оказывает никакого влияния на конечную последовательность.
Идея чередования битов используется во всех блочных и сверточных кодах, рассмотренных здесь и ранее в предыдущих главах. Обычно применяются два типа устройств чередования — блочные и сверточные (оба рассматриваются далее).
а)
__ Пакет __ _
ошибок
X X X X X X X
Рис. 8.10. Пример процедуры чередования битов: а) исходные кодовые слова, содержащие семь кодовых символов;
б) полученные кодовые символы
Блочное устройство чередования принимает кодированные символы блоками от кодера, переставляет их, а затем передает измененные символы на модулятор. Как правило, перестановка блоков завершается заполнением столбцов матрицы М строками и N столбцами (MxN) кодированной последовательности. После того как матрица полностью заполнена, символы подаются на модулятор (по одной строке за раз), а затем передаются по каналу. В приемнике устройство восстановления выполняет обратные операции; оно принимает символы из демодулятора, восстанавливает исходный порядок битов и передает их на декодер. Символы поступают в массив устройства восстановления по строкам и заменяются столбцами. На рис. 8.11, а приведен пример устройства чередования с М = 4 строками и N = 6 столбцами. Записи в массиве отображают порядок, в котором 24 кодовых символа попадают в устройство чередования. Выходная последовательность, предназначенная для передатчика, состоит из кодовых символов, которые построчно удалены из массива, как показано на рисунке. Ниже перечисляются наиболее важные характеристики такого блочного устройства.
1. Пакет, который содержит меньше N последовательных канальных символов, дает на выходе устройства восстановления исходного порядка символов ошибки, разнесенные между собой, по крайней мере, на М символов.
2. Пакет из bN ошибок, где b> 1, дает на выходе устройства восстановления пакет, который содержит не меньше \b \ символьных ошибок. Каждый из пакетов ошибок отделен от другого не меньше, чем на M-Yb\ символов. Запись Гх1 означает наименьшее целое число, не меньшее х, а запись LxJ — наибольшее целое число, не превышающее х.
3. Периодическая последовательность одиночных ошибок, разделенных N символами, дает на выходе устройства восстановления одиночные пакеты ошибок длиной М.
4. Прямая задержка между устройствами чередования и восстановления равна приблизительно длительности 2MN символов. Если быть точным, перед тем как начать передачу, нужно заполнить лишь M(N- 1) + 1 ячеек памяти (как только будет внесен первый символ последнего столбца массива М х N). Соответствующее время нужно приемнику, чтобы начать декодирование. Значит, минимальная прямая задержка будет составлять длительность (2MN - 2М + 2) символов, не учитывая задержку на передачу по каналу.
5. Необходимая память составляет MN символов для каждого объекта (устройств чередования и восстановления исходного порядка). Однако массив MxN нужно заполнить (по большей части) до того, как он будет считан. Для каждого объекта нужно предусмотреть память для 2MN символов, чтобы опорожнить массив MxN, пока другой будет наполняться, и наоборот.
а) |
© | (§) | ||||
© | © | ||||
б) |
© | © | ||||
© | © | © | © | © | © |
в) |
© | |||||
© | |||||
© |
г)
Рис. 8.11. Пример блочного чередования: а) блочное устройство чередования размером М х N; б) пятисимвольный пакет ошибок; в) девятисимволный пакет ошибок; г) периодическая последовательность одиночных ошибок, разнесенных на N = 6 символов
/
Пример 8.4. Характеристики устройства чередования
Используя структуру устройства чередования с М = 4, N=6, изображенную на рис. 8.11, а,
проверьте описанные выше характеристики.
Решение
1. Пусть имеется пакет шума длительностью в пять символьных интервалов; так что символы, выделенные на рис. 8.11, б, подвергнутся искажению во время передачи. После восстановления исходного порядка битов в приемнике, последовательность принимает следующий вид:
Здесь выделенные символы являются ошибочными. Можно видеть, что минимальное расстояние, разделяющее символы с ошибками, равно М = 4.
2. Пусть b = 1,5, так что bN — 9. Пример девятисимвольного пакета ошибок можно видеть на рис. 8.11, в. После того как в приемнике проведена процедура восстановления исходного порядка, последовательность примет следующий вид:
1 2@4 5 6 @ 8 9 10 (П) 12
13 @ © 16 17 ® © 20 21 (3) (§) 24
Снова выделенные символы являются ошибочными. Здесь можно видеть, что пакеты содержат не больше Г 1,5~| = 2 символов подряд и разнесены, по крайней мере, на А/- Ll,5j = 4-1=3 символа.
3. На рис. 8.11, г показана последовательность одиночных ошибок, разделенных (каждый по отдельности) N = 6 символами. После восстановления исходного порядка в приемнике, последовательность принимает следующий вид:
1 2 3 4 5 6 7 8 © (к>) (П) (12)
13 14 15 16 17 18 19 20 21 22 23 24
Можно видеть, что после этого последовательность содержит пакет одиночных ошибок длиной М = 4 символа.
4. Прямая задержка: минимальная прямая задержка, вызванная обоими устройствами, составляет (2MN — 2М + 2) = 42 символьных периода.
5. Требуемый объем памяти: размерность массивов устройств чередования и восстановления составляет MxN. Значит, требуется объем памяти для хранения MN = 24 символов на обоих концах канала. Как упоминалось ранее, в общем случае память реализуется для хранения 2MN = 48 символов.
Как правило, параметры устройства чередования, используемого совместно с кодом с коррекцией одиночных ошибок, выбираются таким образом, чтобы число столбцов N превышало ожидаемую длину пакета. Выбираемое число строк зависит от того, какая схема кодирования будет использована. Для блочных кодов М должно быть больше длины кодового блока; для сверточных кодов М должно превышать длину кодового ограничения. Поэтому пакет длиной N может вызвать в блоке кода (самое большее) одиночную ошибку; аналогично в случае сверточных кодов в пределах одной длины кодового ограничения будет не более одной ошибки. Для кодов с коррекцией ошибок кратности t, выбираемое N должно лишь превышать ожидаемую длину пакета, деленную на t.
8.2.2. Сверточное чередование
Сверточные устройства чередования были предложены Рамси (Ramsey) [7] и Форни (Forney) [8]. Схема, предложенная Форни, показана на рис. 8.12. Кодовые символы последовательно подаются в блок из N регистров; каждый последующий регистр может хранить на J символов больше, чем предыдущий. Нулевой регистр не предназначен для хранения
(символ сразу же передается). С каждым новым кодовым символом коммутатор переключается на новый регистр, и кодовый символ подается на него до тех пор, пока наиболее старый кодовый символ в регистре не будет передан на модулятор/передатчик. После (N - 1)-го регистра коммутатор возвращается к нулевому регистру и повторяет все снова. После приема операции повторяются в обратном порядке. И вход, и выход устройств чередования и восстановления должны быть синхронизированы.
Переключатели Устройство чередования Устройство восстановления Рис. 8.12. Реализация регистра сдвига для сверточного устройства чередования/восстановления |
На рис. 8.13 показан пример простого сверточного четырехрегистрового (/= 1) устройства чередования, загруженного последовательностью кодовых символов. Одновременно представлено синхронизированное устройство восстановления, которое передает обработанные символы на декодер. На рис. 8.13, а показана загрузка символов
1- 4; знак “х” означает неизвестное состояние. На рис. 8.13, б представлены первые четыре символа, подаваемые в регистры, и показана передача символов 5—8 на выход устройства чередования. На рис. 8.13, в показаны поступающие в устройство символы 9-12. Теперь устройство восстановления заполнено символами сообщения, но еще не способно ничего передавать на декодер. И наконец, на рис. 8.13, г показаны символы 13—16, поступившие в устройство чередования, и символы 1—4, переданные на декодер. Процесс продолжается таким образом до тех пор, пока полная последовательность кодового слова не будет передана на декодер в своей исходной форме.
Рабочие характеристики сверточного устройства чередования сходны с параметрами блочного устройства. Важным преимуществом сверточного устройства перед блочным является то, что при сверточном чередовании прямая задержка составляет M(N -1) символов при M = NJ, а требуемые объемы памяти — M(N- 1)/2 на обоих концах канала. Очевидно, что требования к памяти и время задержки снижаются вдвое, по сравнению с блочным чередованием [9].
8.2.3. Каскадные коды
Каскадными называются коды, в которых кодирование осуществляется в два уровня; имеется внутренний и внешний коды, с помощью которых и достигается желаемая надежность передачи сообщений. На рис. 8.14 изображен порядок кодирования и декодирования. Внутренний код связан с модулятором (демодулятором) и каналом; он, как правило, настраивается для исправления большинства канальных ошибок. Внешний код, чаще всего высокоскоростной (с низкой избыточностью), снижает вероят-
ностъ появления ошибок до заданного значения. Основной причиной использования каскадного кода является низкая степень кодирования и общая сложность реализации, меньшая той, которая потребовалась бы для осуществления отдельной процедуры кодирования. На рис. 8.14 между двумя этапами кодирования располагается устройство чередования. Обычно это делается для того, чтобы разнести пакетные ошибки, которые могли бы появиться в результате внутреннего кодирования.
а)
Л Г4 | 5 1 | |||
б) |
-о X -о X -О X -О X |
В) |
-.л А | А „ | ||
-о 13 |
13 9 |
16 12 8 |
г)
Рис. 8.13. Пример сверточного чередования/восстановления
В одной из наиболее популярных систем каскадного кодирования для внутреннего кода применяется сверточное кодирование по алгоритму Витерби, а для внешнего — код Рида- Ссшомона с чередованием между двумя этапами кодирования [2]. Функционирование таких систем при EJN0, находящемся в пределах от 0,2 до 2,5 дБ, для достижения Рв = 10'5 реально достижимо в прикладных задачах [9]. В этой системе демодулятор выдает мягко квантованные кодовые символы на внутренний сверточный декодер, который, в свою очередь, выдает жестко квантованные кодовые символы с пакетными ошибками на декодер Рида-Соломона.
Входные данные Декодированные данные Рис. 8.14. Блочная диаграмма каскадной системы кодирования |
(В системе декодирования по алгоритму Витерби выходные ошибки имеют тенденцию к появлению пакетами.) Внешний код Рида-Соломона образуется из m-битовых сегментов двоичного потока данных. Производительность такого (недвоичного) кода Рида-Соломона зависит только от числа символьных ошибок в блоке. Код не искажается пакетами ошибок внутри m-битового символа. Иными словами, для данной символьной ошибки производительность кода Рида-Соломона такова, как если бы символьная ошибка была вызвана одним битом или т бит. Тем не менее производительность каскадных систем несколько ухудшается за счет коррелирующих ошибок в последовательных символах. Поэтому чередование между кодированиями нужно выполнять на уровне символов (а не битов). Работа [10] представляет собой обзор каскадных кодов, которые были разработаны для дальней космической связи. В следующем разделе мы рассмотрим распространенную практическую реализацию символьного чередования в каскадных системах.
8.3. Кодирование и чередование в системах цифровой записи информации на компакт-дисках
В 1979 году компании Philips Corp. (Нидерланды) и Sony Corp. (Япония) запатентовали стандарт хранения и воспроизведения цифровой записи аудиосигналов, известный как система цифровой записи на компакт-дисках (compact disc digital audio — CD-DA). Эта система стала мировым стандартом, позволяющим достичь безукоризненной точности воспроизведения звука, и опередила другие методики. Для хранения оцифрованных аудиосигналов используется пластиковый диск диаметром 120 мм. Сигнал дискретизирован с частотой 44100 фрагментов/с для получения записи в полосе 20 кГц. Каждый аудиофрагмент однозначно квантован на один из 216 уровней (16 бит/фрагмент), что дает в результате динамический диапазон в 96 дБ и нелинейное искажение 0,005%. Отдельный диск (время звучания составляет порядка 70 минут) хранит порядка 10ю бит в виде коротких впадин, которые сканируются лазером.
В данном случае существует несколько источников канальных ошибок: 1) маленькие нежелательные частички или воздушные пузырьки в материале пластика или неточное расположение впадин при изготовлении диска; 2) отпечатки пальцев или цара
пины, появившиеся при эксплуатации. Трудно предсказать, как в среднем можно повредить компакт-диск; но при наличии точной канальной модели можно со всей уверенностью сказать, что канал, в основном, склонен вносить пакетоподобные ошибки, поскольку царапины или пятна от пальцев будут вызывать ошибки в нескольких последовательных фрагментах данных. Важным элементом разработки системы получения высококачественных характеристик является каскадная схема защиты от ошибок, которая называется кодом Рида-Соломона с перекрестным чередованием (cross-interleave Reed-Solomon code — CIRC). Данные перемешиваются во времени так, что знаки, выходящие из последовательных фрагментов сигнала, оказываются разнесенными во времени. Таким образом, появление ошибок представляется в виде одиночных случайных ошибок (см. предыдущий раздел). Цифровая информация защищена посредством прибавления байтов четности, получаемых в двух кодерах Рида-Соломона. Защита от ошибок, осуществляемая на компакт-дисках, зависит обычно от кодирования Рида- Соломона и алгоритма чередования.
В прикладных задачах передачи цифровой аудиоинформации, невыявляемая ошибка декодирования очень значительна, поскольку является результатом щелчка при воспроизведении, в то время как выявляемые ошибки незначительны, так как их можно скрыть. Схема защиты от ошибок CIRC в системе CD-DA включает в себя и исправление, и маскировку ошибок. Технические характеристики схемы CIRC даются в табл. 8.4. Из данных таблицы должно быть ясно, что компакт-диск может выдержать сильные повреждения (например, 8-миллиметровые отверстия, пробитые в диске) без значительных потерь в качестве звучания.
Таблица 8.4. Спецификация кода Рида-Соломона с перекрестным чередованием, применяемого в аудиокомпакт-дисках
Максимальная длина исправимого пакета «* 4000 бит (2,5 мм длины дорожки на диске)
Максимальная длина пакета, который можно = 12000 бит (8 мм) интерполировать
Скорость интерполяции фрагмента i фрагмент/10 часов при Рв = КГ[5];
1000 фрагментов/мин. при Рв = 10~[6]
Необнаруженные фрагменты с ошибками Менее чем 1 на 750 часов при Рв = 10~3
(щелчки) Пренебрежимо малое количество при Рв< 10~*
Качество нового диска рв = Ю-4
На рис. 8.15 показана основная блочная диаграмма кодера CIRC (с оборудованием для записи компакт-диска) и декодера (с оборудованием для воспроизведения компакт-диска). Процедура кодирования состоит из собственно кодирования и чередования, где введены следующие обозначения: Д-чередование, С2-кодирование, D*- чередование, Сгкодирование и D-чередование. Процедура декодирования состоит из этапов декодирования и восстановления исходного порядка битов, которые выполняются в обратном порядке; здесь идут D-восстановление, Ct-декодирование, £>*- восстановление, С2-декодирование и Д-восстановление.
На рис. 8.16 показан элементарный период системного кадра и шесть периодов дискретизации, каждый из которых состоит из пары стереофрагментов (16-битовый левый фрагмент и 16-битовый правый фрагмент). Биты собраны в символы или байты размером 8 бит каждый. Следовательно, каждая пара фрагментов содержит 4 байт, а некоди- рованный кадр — к = 24 байт. На рис. 8.16, а~д представлены пять этапов кодирования, которые характеризуют систему CIRC. Функции каждого этапа будут более понятны, если мы рассмотрим процедуру декодирования. Этапы выглядят следующим образом.
а) A-чередование. Четные фрагменты отделяются от нечетных двумя кадрами для перемешивания ошибок, которые определены, но нельзя исправить. Это облегчает процесс интерполяции.
б) Сг-кодирование. К Д-чередованному 24-байтовому кадру прибавляется четыре байта четности Рида-Соломона, что дает в итоге п = 28 байт. Такой код (28, 24) называется внешним.
в) D*-чередование. Здесь каждый байт задерживается на разную длину; таким образом ошибки разбрасываются на несколько кодовых слов. С2-кодирование совместно с D*-чередованием нужно для исправления пакетных ошибок и моделей ошибки, которые Сгдекодер не в состоянии исправить.
г) С г кодирование. К к = 28 байт 0*-чередованного кадра прибавляется четыре байта четности Рида-Соломона, что дает в итоге всего п = 32 байт. Такой код (32, 28) называется внутренним.
Дата добавления: 2015-10-28; просмотров: 48 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Основы теории принятая статистических решений 1051 40 страница | | | Основы теории принятая статистических решений 1051 42 страница |