Вернер М. Основы кодирования (2004) (1151882), страница 37
Текст из файла (страница 37)
4.25. Ограничимся рассмотрением канала с одним элементомзадержки D. В этом случае возможны два состояния канала 5Ь и Si.^260Глава 4- Сверточпые кодыТаблица 4.9. Состояние канала с МСИ и уровни сигналов.Символ на входе Значение Состояниеd[n]XI [fl]S[n]-1-1Sov[n]-0,7-0,3= -l,0 = do+0,7-0,3 = +0,4 = di1-1-1Уровень1-0,7 + 0,3 = -0,4 = d2Si+0,7 + 0,3 = +1,0 = d3+1Пусть последовательность сигналов d[n] состоит из биполярных символовd[n]e{-l,l}.•(4.81)Выберем коэффициенты /о и f\ равными/о = 0,7 и Л = 0 , 3 .(4.82)В таблице 4.9 для входных символов d[n] в зависимости от значенияxi[n], определяющей состояние канала So и Si, приведены уровнинезашумленных сигналов v[n].
Согласно модели канала рис. 4.25 кэтим сигналам добавляется гауссовский шум г[п]. На входе детектора мы имеем сигнал z[n] с нормальным распределением и среднимизначениями из {^0,^1,^2,^3} (табл. 4.9).На каждом такте декодер сравнивает величину z[n] с уровнямисигнала из {do,di,d2,d$} и вычисляет метрики соответствующих переходов между состояниями канала. Исходя из принципа максимального правдоподобия и нормального распределения z[n], в качествеметрик выбираются величиныXi = {z-2di) .(4.83)На сетевой диаграмме (рис. 4.26) показаны состояния канала, переходы между ними и приращения текущих метрик, соответствующиеэтим переходам.После предварительных замечаний рассмотрим численный пример работы детектора Витерби.
В таблице 4.10 приведены последовательность входных сигналов, уровни принимаемых незашумленныхсимволов и последовательность сигналов на входе детектора. Работадетектора Витерби представлена на рис. 4.27.Детектор Витерби на сетевой диаграмме рис. 4. 27 начинает декодирование на первом такте из состояния Si (на нулевом такте канал4-7. Детектор Витерби261принудительно переводится в это состояние путем передачи «+1»).На первом такте возможны только два перехода.
Найдем приращения метрик на этих переходах и нанесем их на сетевую диаграммуA3 = ( 2 - d 3 ) 2 = ( 2 , 2 - l ) 2 = l,44А2 = ( z - d 2 ) 2 = (2,2 + 0,4) 2 =6,76.(4.84)Рис. 4.26. Переходы между состояниями и приращенияметрик.Таблица 4.10. Передача информации по каналу с МСИ.Такт п011234567891011121-11-1111-1-1-1120,4-0,40,4Символ d[n]IКанал v[n]0,7 1,0 -0,41,0 1,0 -0,4 -1,0 -1,00,4 0,3Принято z[n 1,1 2,2 0,02 -0,06 -ОДЗ -0,31 0,99 0,97 -0,40 -1.2 -0,23 -0,93 0,612Инициализация (посылаемый бит известен приемнику).Замирание.Так как на первом такте не происходит слияния альтернативныхпутей, приращения метрик непосредственно заносятся в регистрыметрик оптимальных путей для состояний SQH S\.B регистры путейдля состояний So и Si заносятся соответственно «0» и «1».На втором такте декодирования возможны уже все переходы.Найдем приращения метрик для всех четырех переходов и для продолжения выберем путь с наименьшей метрикой.
Так как для первого входного бита произошло слияние путей для состояний So и S\,будем считать первый принятый бит продетектированным.Продолжая этот процесс далее, продетектируем всю последовательность входных символов.^262Глава 4- Сверточные кодыНесмотря на значительное воздействие на детектируемый сигналшумовой компоненты, вес символы продетектированы правильно.Начальноесосто ие 1.44S)\Ж а96® \ \ 0,18/6.76 I/0[2J911\\/ 0.14V "•'ML1.04Ж/ш0.21/ом0.882,46000.760,00Рис.
4.27. Сетевая диаграмма детектора Витерби.4.8. УпражненияУпражнение 4.1: Сверточный код.1. Найдите порождающий многочлен двоичного сверточного кода, обладающего максимальным свободным расстоянием, соскоростью R = 1/2 и длиной кодового ограничения пс = 6;2. Приведите схему кодера;3. Нарисуйте диаграмму состояний;4. Проведите кодирование информационной последовательности{м[п]} = {1,0,0,1,1,0,1} с лсмощью диаграммы состояний.Для этого, прежде всего, найдите последовательность состояний, считая, что процедура кодирования начинается и заканчивается в нулевом состоянии;5. Предположим, что принята последовательность01,11,01,10, 10,10,01,11}.
Проведите декодирование даннойпоследовательности по максимуму правдоподобия с помощью4-8. Упражнениясетевой диаграммы состояний; Указание: при декодированииучтите, что кодирование начиналось и заканчивалось нулевымсостоянием.6. Как может быть интерпретирована метрика декодированнойинформационной последовательности?Упражнение 4.2: Сверточный код, используемый в сети мобильной связи GSM.Для передачи речи в сетях мобильной связи GSM используется оптимальный сверточный код с производящими многочленамиЯ\ (х) = 1 + хл + хл и д2 (х) = 1 + х + х3 + х4, имеющий свободноерасстояние, равное d/ree = 71. Приведите схему кодера, содержащую переменные х\, Х2, хз, х\.2.
Каждый речевой блок, продолжительностью 20 мсек, содержащий 185 бит, кодируется сверточным кодом. Сколько нулейнужно добавить к информационной последовательности длятого, чтобы кодирование закончилось в нулевом состоянии?3. Определите значения следующих величин: памяти кодера, кодового ограничения, блоковой скорости, относительной потерискорости, полной памяти кодера.4. Оцените сложность реализации декодера Витерби.Упражнение 4.3: Сверточный код, используемый в сети мобильной связи GSM.Для передачи данных в сети GSM со скоростью 4,8 кбит/сек поканалу TCH/F4,8 используется сверточный код с порождающими3424многочленами д\{х) = 1 + х + х + а; , д2(х) = 1 + х + х и дз(х) =2341 + х + х + х + х с dfree = 12.1. Приведите схему кодера, содержащую переменные хi,a;2, хз,Xi.2.
Из технических соображений каждый информационный блок,содержащий 60 бит, кодируется словом, длина которого составляет 228 бит. Сколько нулевых бит добавляется в конце информационного блока? Каким состоянием заканчивается декодирование?3. Определите значение памяти кодера, кодового ограничения,блоковой скорости кода, относительной потери кодовой скорости, полной памяти кодера.,264Глава 4- Сверточные коды4. Оцените сложность реализации декодера Витерби.Упражнение 4.4: Детектор Витерби с субонтимальной метрикой.Повторите ранее рассмотренный пример работы детектора Витерби при субоптимальной метрикеXi=\z-di\.Решения заданий.Решение задания 4.1. Сверточный код.1. Для заданных параметров из таблицы находим порождающиемногочлены д\{х) = 1 + ж2; д2(х) = 1 + х + х2.2. Схема кодера.3. Диаграмма состояний кодера0/001/114. Кодирование информационной последовательности.Из диаграммы состояний получаем:Последовательность состояний (старт So) — Si — S2 — So — SiS3-S2Si(-S2 - 50«XBOCT»).Кодовое слово {v[n]} = {11,01,11,11,10,10,00,01,11}4-8.
Упражнения 265]5. Декодирование по сетевой диаграмме с минимальным расстоянием ХэммингаПринятое слово {r[n]}' = {11,01,11,01,10,10,01,10,11}22 I .JПродекодйрованная информационная последовательность{«'[n]} = {1,0,0,1,1,0,1}6. Если переданное слово иродекодированно правильно, то метрику полученного кодового слова можно интерпретировать какчисло ошибочных бит и в этом с дучае метрика может быть использована для оценки качества, канала.Решение задания 4.2. Сверточньгй: код, используемый для кодирования речи в сетях мобильной связи GSM.1. Схема кодера•—о—•—э—>-2.
К информационной последовательности необходимо добавить4 нуля для того, чтобы кодирование заканчивалось нулевымсостоянием.3. Память кодера т = 4.Кодовое ограничение пс = 10.Глава 4- Сверточные кодыБлоковая скорость 185/(2[185 + 4]) = 0,489Относительная потеря скорости 4/(185 + 4) = 2,11 • 10~2Полная память кодера М = 4.4. Существует 2 м = 16 состояний. На каждом шаге декодер вычисляет 32 приращения метрик, исходя из которых вычисляются тридцать две частичных метрики и сравниваются попарно;16 вцживших путей выбираются для продолжения и их частичные метрики запоминаются.Решение задания 4.3. Сверточный код для передачи данных вмобильных сетях связи GSM.1.
Схема кодера2. Из равенства 3- (60+х) = 228 следует, что х = 16, т.е. к инфор_ мационной последовательности добавляются 16 нулей и кодирование заканчивается нулевым состоянием.60+лКодер228Л =1/33. Память кодера т = 4. Кодовое ограничение пс = 3-(4+1) = 15.Блоковая скорость 60/(3 • [60 + 4]) = 0,3125- учитывая 16 нулевых бит получаем 60/228 = 0,263Относительная потеря скорости 4/64 = 6,25 • 10~2- учитывая 16 нулевых бит получаем 16/76 = 0,211Полная память кодера М = 4.4. Существует Iм = 16 состояний.
В каждом такте декодер вычисляет 32 приращения метрик, исходя из которых вычисляются и попарно сравниваются 32 частичные метрики; 16 полученных путей выбираются для продолжения и их частичныеметрики запоминаются.4-8. Упражнения 267]Решение задания 4.4. Детектор Витерби с субоптимальной аддитивной метрикой.Таким образом, при аддитивной метрике информационная последовательность также детектируется без ошибок.ГЛАВА 5ДИСКРЕТНЫЕПРЕОБРАЗОВАНИЯ ФУРЬЕИ КОДЫ РИДА - СОЛОМОНА5.1. ВведениеВ предыдущих главах мы рассматривали только двоичные коды, тоесть коды с символами из GF(2). Между тем, коды над алфавитомGF(q), где q > 2, так называемые g-ичные коды, помимо чисто теоретического интереса, имеют в настоящее время огромное прикладноезначение. Мы ограничимся только рассмотрением кодов Рида - Соломона, как наиболее ярких представителей д-ичных кодов, без которых немыслима современная теория и практика помехоустойчивогокодирования.Остановимся, прежде всего, на прикладном значении кодов Рида - Соломона.
Как было показано в предыдущих главах, простейшие алгебраические двоичные коды могут успешно применяться дляпередачи данных в компьютерных сетях связи, обеспечивая необходимую надежность передаваемой информации. Это объясняется достаточно высоким качеством проводных и оптоволоконных каналовсвязи и возможностью переспроса передаваемых блоков данных.
Задача кодирования для таких каналов, в основном, сводится только кобнаружению независимых ошибок и пакетов ошибок.Все многообразие современных коммуникационных линий связине исчерпывается только компьютерными сетями. В качестве примеров достаточно привести спутниковые каналы и мобильную цифровую связь. Здесь уже переспросы не допустимы и корректирующая способность кода определяется максимальным числом исправляемых ошибок. Предельная мощность передаваемого сигнала в таких каналах жестко ограничивается, что приводит к высокой вероятности появления как независимых ошибок, так и пакетов ошибок.В таких каналах использование рассмотренных нами простейшихдвоичных кодов не имеет смысла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
