Основы теории принятая статистических решений 1051 36 страница

  Рис. 7.9. Двоичный симметричный канал (канал с же­сткой схемой принятия решений)

Пусть U⁽"° — это переданное по каналу BSC кодовое слово с вероятностью появле­ния ошибочного символа р, Z — соответствующая последовательность, полученная декодером. Как отмечалось ранее, декодер, работающий по принципу максимального правдоподобия, выбирает кодовое слово U^<m), имеющее максимальное правдоподобие Р(Z|U⁽'”⁾) или его логарифм. Для BSC это эквивалентно выбору кодового слова U⁽'”⁾, находящегося на наименьшем расстоянии Хэмминга от Z [8]. Расстояние Хэмминга — это удобная метрика для описания расстояния или степени сходства между U^(m) и Z. Из всех возможных переданных последовательностей U^(m) декодер выбирает такую по­следовательность U^(m,), для которой расстояние до Z минимально. Предположим, что каждая из последовательностей и^<т) и Z имеет длину L бит и отличается на d_m позиций (т.е. расстояние Хэмминга между и^<т) и Z равно d_m). Тогда, поскольку предполагалось, что канал не имеет памяти, вероятность того, что U^(m) преобразовалось в Z, находя­щееся на расстоянии d_m от и*"⁰, может быть записана в следующем виде:

P(Z\\J^im)) = p^d"'(\-p)^L~^d'’'. (7.6)

Логарифмическая функция правдоподобия будет иметь следующий вид:

Ig P(Z|U^(m)) = -d_m + i-lgfl - P) • (7.7)

Если вычислить эту величину для каждой возможно переданной последовательности, последнее слагаемое в уравнении будет постоянным для всех случаев. Если предполо­жить, что р < 0,5, уравнение (7.7) можно записать в следующей форме:

lgP(Z\\f^m)) = -Ad_m-B. (7.8)

Здесь А и В — положительные константы. Следовательно, такой выбор кодового слова U^<"^,), чтобы расстояние Хэмминга до полученной последовательности Z было мини­мальным, соответствует максимизации метрики правдоподобия или логарифма правдопо­добия. Следовательно, в канале BSC метрика логарифма правдоподобия легко заменя­ется расстоянием Хэмминга, а декодер, работающий по принципу максимального правдоподобия, будет выбирать на древовидной или решетчатой диаграмме путь, со­ответствующий минимальному расстоянию Хэмминга между последовательностью и^<т’⁾ и полученной последовательностью Z.

7.3.2.2. Гауссов канал

Для гауссова канала каждый выходной символ демодулятора Zj„ как показано на рис. 7.1, принимает значения из непрерывного алфавита. Символ z_Jt нельзя пометить

для детектирования как правильное или неправильное решение. Передачу на декодер таких мягких решений можно рассматривать как поступление семейства условных ве­роятностей различных символов (см. раздел 6.3.1). Можно показать [8], что максими­зация P(Z\U^lm>) эквивалентна максимизации скалярного произведения последователь­ности кодовых слов I/"⁰ (состоящей из двоичных символов, представленных как би­полярные значения) и аналогового значения полученной последовательности Z. Таким образом, декодер выбирает кодовое слово если выражение

(7.9)

имеет максимальное значение. Это эквивалентно выбору кодового слова U^(m,), нахо­дящегося на ближайшем евклидовом расстоянии от Z. Даже несмотря на то что каналы с жестким и мягким принятием решений требуют различных метрик, концепция вы­бора кодового слова Ц^, ближайшего к полученной последовательности Z, одинакова для обоих случаев. Чтобы в уравнении (7.9) точно выполнить максимизацию, декодер должен осуществлять арифметические операции с аналоговыми величинами. Это не­практично, поскольку обычно декодеры являются цифровыми. Таким образом, необ­ходимо дискретизировать полученные символы z_Jt. Не напоминает ли вам уравнение (7.9) демодуляционную обработку, рассмотренную в главах 3 и 4? Уравне­ние (7.9) является дискретным вариантом корреляции входного полученного сигнала КО с опорным сигналом 5,(0, которая выражается уравнением (4.15). Квантованный гауссов канал, обычно называемый каналом с мягкой схемой решений, — это модель канала, в которой предполагается, что декодирование осуществляется на основе опи­санной ранее мягкой схемы принятия решения.

7.3.3. Алгоритм сверточного декодирования Витерби

В 1967 году Витерби разработал и проанализировал алгоритм [13], в котором, по сути, реализуется декодирование, основанное на принципе максимального правдо­подобия; однако в нем уменьшается вычислительная нагрузка за счет использова­ния особенностей структуры конкретной решетки кода. Преимущество декодирова­ния Витерби, по сравнению с декодированием по методу “грубой силы”, заключа­ется в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычис­ление меры подобия (или расстояния), между сигналом, полученным в момент времени t„ и всеми путями решетки, входящими в каждое состояние в момент времени ti. В алгоритме Витерби не рассматриваются те пути решетки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть опти­мальными. Если в одно и то же состояние входят два пути, выбирается тот, кото­рый имеет лучшую метрику; такой путь называется выживающим. Отбор выжи­вающих путей выполняется для каждого состояния. Таким образом, декодер уг­лубляется в решетку, принимая решения путем исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декоди­рования. В 1969 году Омура (Omura) [14] показал, что основу алгоритма Витер­би составляет оценка максимума правдоподобия. Отметим, что задачу отбора оп­тимальных путей можно выразить как выбор кодового слова с максимальной мет­рикой правдоподобия или минимальной метрикой расстояния.

Для простоты предположим, что мы имеем дело с каналом BSC; в таком случае приемлемой мерой расстояния будет расстояние Хэмминга. Кодер для этого приме­ра показан на рис. 7.3, а решетчатая диаграмма — на рис. 7.7. Для представления декодера, как показано на рис. 7.10, можно воспользоваться подобной решеткой. Мы начинаем в момент времени г, в состоянии 00 (вследствие очистки кодера меж­ду сообщениями декодер находится в начальном состоянии). Поскольку в этом примере возможны только два перехода, разрешающих другое состояние, для начала не нужно показывать все ветви. Полная решетчатая структура образуется после мо­мента времени г₃. Принцип работы происходящего после процедуры декодирования можно понять, изучив решетку кодера на рис. 7.7 и решетку декодера, показанную на рис. 7.10. Для решетки декодера каждую ветвь за каждый временной интервал удобно пометить расстоянием Хэмминга между полученным кодовым символом и кодовым словом, соответствующим той же ветви из решетки кодера. На рис. 7.10 показана последовательность сообщений т, соответствующая последовательности кодовых слов U, и искаженная шумом последовательность Z= 11 01 01 10 01.... Как показано на рис. 7.3, кодер характеризуется кодовыми словами, находящимися на ветвях решетки кодера и заведомо известными как кодеру, так и декодеру. Эти сло­ва являются кодовыми символами, которые можно было бы ожидать на выходе ко­дера в результате каждого перехода между состояниями. Пометки на ветвях решетки декодера накапливаются декодером в процессе. Другими словами, когда получен ко­довый символ, каждая ветвь решетки декодера помечается метрикой подобия (расстоянием Хэмминга) между полученным кодовым символом и каждым словом ветви за этот временной интервал. Из полученной последовательности Z, показан­ной на рис. 7.10, можно видеть, что кодовые символы, полученные в (следующий) момент времени г_ь — это 11. Чтобы пометить ветви декодера подходящей метрикой расстояния Хэмминга в (прошедший) момент времени t_u рассмотрим решетку ко­дера на рис. 7.7. Видим, что переход между состояниями 00 -» 00 порождает на вы­ходе ветви слово 00. Однако получено 11. Следовательно, на решетке декодера по­мечаем переход между состояниями 00 -» 00 расстоянием Хэмминга между ними, а именно 2. Глядя вновь на решетку кодера, видим, что переход между состояниями 00 -» 10 порождает на выходе кодовое слово 11, точно соответствующее полученно­му в момент г, кодовому символу. Следовательно, переход на решетке декодера ме­жду состояниями 00 -» 10 помечаем расстоянием Хэмминга 0. В итоге, метрика входящих в решетку декодера ветвей описывает разницу (расстояние) между тем, что было получено, и тем, что “могло бы быть” получено, имея кодовые слова, свя­занные с теми ветвями, с которых они были переданы. По сути, эти метрики опи­сывают величину, подобную корреляциям между полученным кодовым словом и каждым из кандидатов на роль кодового слова. Таким же образом продолжаем помечать ветви решетки декодера по мере получения символов в каждый момент времени В алгоритме декодирования эти метрики расстояния Хэмминга ис­пользуются для нахождения наиболее вероятного (с минимальным расстоянием) пути через решетку.

Смысл декодирования Витерби заключается в следующем. Если любые два пути сливаются в одном состоянии, то при поиске оптимального пути один из них всегда можно исключить. Например, на рис. 7.11 показано два пути, сливающихся в момент времени t_s в состоянии 00.

"7 Q rtiArtii4\1пмг\Апi/о чопчии! лпоптлиилгл 1/лп14Пппои)/1а

Входная информационная последовательность	т:
Переданные кодовые слова	U:
Принятая последовательность	Z:
Состояние а =	fi 00 «г-		f2 —*г-		f3 —«Г-		f4 1	f5 1 f6

b= 10 •

c = 01 •

d = 11 •

. /m Метрика V 2 ^ветви

Рис. 7.10. Решетчатая диаграмма декодера (степень кодирования 1/2, К= 3)

Давайте определим суммарную метрику пути по Хэммингу для данного пути в мо­мент времени г, как сумму метрик расстояний Хэмминга ветвей, по которым про­ходит путь до момента t,. На рис. 7.11 верхний путь имеет метрику 4, нижний — метрику 1. Верхний путь нельзя выделить как оптимальный, поскольку нижний путь, входящий в то же состояние, имеет меньшую метрику. Это наблюдение поддерживается Марковской природой состояний кодера. Настоящее состояние завершает историю кодера в том смысле, что предыдущие состояния не могут по­влиять на будущие состояния или будущие ветви на выходе.

и

ходное состояние решетки. (Это предположение не является необходимым, одна­ко упрощает объяснения.) В момент времени t_{ получены кодовые символы 11. Из состояния 00 можно перейти только в состояние 00 или 10, как показано на рис. 7.12, а. Переход между состояниями 00 -» 10 имеет метрику ветви 0; переход между состояниями 00 00 — метрику ветви 2. В момент времени t₂ из каждого состояния также может выходить только две ветви, как показано на рис. 7.12, 6. Суммарная метрика этих ветвей обозначена как метрика состояний Г„, r_fc, Г_с и T_d, соответствующих конечным состояниям. В момент времени г₃ на рис. 7.12, в опять есть две ветви, выходящие из каждого состояния. В результате имеется два пути, входящих в каждое состояние, в момент времени г₄. Один из путей, входя­щих в каждое состояние, может быть исключен, а точнее — это путь, имеющий большую суммарную метрику пути. Если бы метрики двух входящих путей имели одинаковое значение, то путь, который будет исключаться,,выбирался бы произ­вольно. Выживший путь в каждом состоянии показан на рис. 7.12, г. В этой точке процесса декодирования имеется только один выживший путь, который называет­ся полной ветвью, между моментами времени t_x и t₂. Следовательно, декодер те­перь может решить, что между моментами t\ и г₂ произошел переход 00 -» 10. По­скольку переход вызывается единичным входным битом, на выходе декодера пер­вым битом будет единица. Здесь легко можно проследить процесс декодирования выживших ветвей, поскольку ветви решетки показаны пунктирными линиями для входных нулей и сплошной линией для входных единиц. Заметим, что первый бит не декодируется, пока вычисление метрики пути не пройдет далее вглубь решет­ки. Для обычного декодера такая задержка декодирования может оказаться раз в пять больше длины кодового ограничения в битах.

На каждом следующем шаге процесса декодирования всегда будет два пути для каждого состояния; после сравнения метрик путей один из них будет исключен. Этот шаг в процессе декодирования показан на рис. 7.12, д. В момент t₅ снова имеется по два входных пути для каждого состояния, и один путь из каждой пары подлежит исключению. Выжившие пути на момент ц показаны на рис. 7.12, е. Заметим, что в нашем примере мы еще не можем принять решения относительно второго входного информационного бита, поскольку еще остается два пути, исхо­дящих в момент t₂ из состояния в узле 10. В момент времени t₆ на рис. 7.12, ж снова можем видеть структуру сливающихся путей, а на рис. 7.12, з — выжившие пути на момент г₆. Здесь же, на рис. 7.12, з, на выходе декодера в качестве вто­рого декодированного бита показана единица как итог единственного оставшего­ся пути между точками /₂ и /₃. Аналогичным образом декодер продолжает углуб­ляться в решетку и принимать решения, касающиеся информационных битов, устраняя все пути, кроме одного.

Отсекание (сходящихся путей) в решетке гарантирует, что у нас никогда не будет путей больше, чем состояний. В этом примере можно проверить, что после каждого отсекания (рис. 7.12, б—д) остается только 4 пути. Сравните это с попыткой приме­нить “грубую силу” (без привлечения алгоритма Витерби) при использовании для получения последовательности принципа максимального правдоподобия. В этом случае число возможных путей (соответствующее возможным вариантам последова­тельности) является степенной функцией длины последовательности. Для двоичной последовательности кодовых слов с длиной кодовых слов L имеется 2¹ возможные последовательности.

6)

Метрики

состояний

fi

а = 00 •.

fi а = 00 Ь = 10» с = 01 • d = 11 •

Рис. 7.12. Выбор выживших путей: а) выжившие на момент /₂; б) выжившие на момент 1_Ъ; в) сравнение метрик в момент t_A; г) выжившие на момент Г₄; д) срав­нение метрик в момент t_s; е) выжившие на момент t_s; ж) сравнение метрик в момент t₆; з) выжившие на момент t₆

В контексте решетчатой диаграммы, показанной на рис. 7.10, переходы за один проме­жуток времени можно сгруппировать в 2^V'‘ непересекающиеся ячейки; каждая ячейка будет изображать четыре возможных перехода, причем v = К- 1 называется памятью ко­дера (encoder memory). Если К-Ъ, то v = 2, и, следовательно, мы имеем 2^V~^X - 2 ячейки. Эти ячейки показаны на рис. 7.13, где буквы а, Ь, с Hd обозначают состояния в момент t„ а а', Ь', с’ и с? — состояния в момент времени *,+Для каждого перехода изображена метрика ветви индексы которой означают переход из состояния х в состояние у. Эти ячейки и соответствующие логические элементы, которые корректируют метрики со­стояний {Г_х}, где х означает конкретное расстояние состояния, представляют основные составляющие элементы декодера.

Ячейка 1 Ячейка 2   Рис. 7.13. Примеры ячеек декодера

7.3.5.1. Процедура сложения, сравнения и выбора

Вернемся к примеру двух ячеек с К = 3. На рис. 7.14 показан логический блок, со­ответствующий ячейке 1. Логическая схема осуществляет специальную операцию, ко­торая называется сложение, сравнение и выбор (add-compare-select — ACS). Метрика состояния Г_я- вычисляется путем прибавления метрики предыдущего состояния а, Г,„ к метрике ветви 5„„- и метрики предыдущего состояния с, Г,., к метрике ветви 5,_у,- Это даст в результате две метрики путей в качестве кандидатов для новой метрики состоя­ния Г„-. Оба кандидата сравниваются в логическом блоке, показанном на рис. 7.14. Наиболее правдоподобная из двух метрик путей (с наименьшим расстоянием) запо­минается как новая метрика состояния Г,,- для состояния а'. Также сохраняется новая история путей т_а. для состояния а, где т_а- — история пути информации для данного состояния, дополненная сведениями о выжившем пути.

На рис. 7.14 также показана логическая схема ACS для ячейки 1, которая дает но­вую метрику состояния Г*- и новую историю состояния т_ь<. Операция ACS аналогич­ным образом осуществляется и для путей в других ячейках. Выход декодера составля­ют последние биты на путях с наименьшими метриками состояний.

7.3.5.2. Вид процедуры сложения, сравнения и выбора на решетке

Рассмотрим тот же пример, которым мы воспользовались в разделе 7.3.4 для опи­сания декодирования на основе алгоритма Витерби. Последовательность сообщений имела вид m = 1 1 0 1 1, последовательность кодовых слов — U = 11 01 01 00 01, а при­нятая последовательность — Z = 11 01 01 10 01.

7 3 СЬппмупмппикгя тапячы трптпчнпгп кГППИППИЯНИЯ

  К следующему логическому элементу К следующему логическому элементу Рис. 7.14. Логический блок, предназначенный -для осуществления операции сложения, сравнения и выбора

Решетчатая диаграмма декодирования, аналогичная показанной на рис. 7.10, изображена на рис. 7.15. Метрика ветви, которая описывает каждую ветвь, — это расстояние Хэм­минга между принятым кодовым символом и соответствующим кодовым словом из ре­шетки кодера. Еще на решетке (рис. 7.15) показаны значения каждого состояния х в ка­ждый момент t₂—t₆, метрика состояния которых обозначена Т_х. Операция ACS выполня­ется после появления двух переходов, входящих в состояние, т.е. для момента /₄ и более поздних. Например, в момент времени /₄ значение метрики состояния для состояния а вычисляется суммированием метрики состояния Г„ = 3 в момент?₃ и метрики ветви 8^=1, что в итоге дает значение 4. В то же время к метрике состояния Г_г = 2 в мо­мент времени t₃ прибавляется метрика ветви 8_га- = 1, что дает значение 3. В ходе про­цедуры ACS происходит отбор наиболее правдоподобной метрики (с минимальным расстоянием), т.е. новой метрики состояния; поэтому для состояния а в момент г₄ но­вой метрикой состояния будет Г„- = 3. Отобранный путь изображен жирной линией, а путь, который был отброшен, показан светлой линией. На рис. 7.15 на решетке слева направо показаны все метрики состояний. Убедимся, что в любой момент времени значение каждой метрики состояния получается суммированием метрики состояния, соединенного с предыдущим состоянием вдоль отобранного пути (жирная линия), и метрики ветви, соединяющей эти состояния. Через некоторое время на выход деко­дера будут поданы выжившие ветви, прослеженные до самых ранних битов. Чтобы показать это, посмотрим на рис. 7.15 в момент /₆. Видим, что значение метрики со­стояния, соответствующей минимальному расстоянию, равно 1. Отобранный путь можно проследить из состояния d обратно, к моменту t_u и убедиться, что декодиро­ванное сообщение совпадает с исходным. Напомним, что пунктирные и сплошные линии соответствуют двоичным единице и нулю.

7.3.6. Память путей и синхронизация

Требования к памяти декодера, работающего согласно алгоритму Витерби, растут с увеличением длины кодового ограничения как степенная функция. Для кода со сте­пенью кодирования 1/я после каждого шага декодирования декодер держит в памяти набор из 2^К~¹ путей.

fi t2 t3 Ц ts te   Puc. 7.15. Операция сложения, сравнения и выбора при декодировании по алгоритму Витерби

]

С высокой степенью вероятности можно утверждать, что при значительном превы­шении существующей на данный момент глубины декодирования эти пути не будут взаимно непересекающимися [12]. Все 2^ЛГ~¹ пути ведут к полной ветви, которая в конце концов разветвляется на разные состояния. Поэтому, если декодер сохраняет историю 2^К~¹ путей, самые первые биты на всех путях будут одинаковы. Следова­тельно, простой декодер имеет фиксированный объем истории путей и выдает самые ранние биты произвольного пути каждый раз, когда продвигается на один уровень вглубь решетки. Требуемый объем сохраняемых путей будет равен следующему [12]:

и = hl^K~(7.10)

Здесь h — длина истории пути информационного бита на состояние. При уточне­нии, которое проводится для минимизации h, вместо самых ранних битов произ­вольных путей на выходе декодера используются самые ранние биты наиболее ве­роятных путей. Было показано [12], что значения h, равного 4 или 5 длинам ко­дового ограничения, достаточно, чтобы характеристики декодера были близки к оптимальным. Необходимый объем памяти и является основным ограничением при разработке декодеров, работающих согласно алгоритму Витерби. В серийно выпускаемых декодерах длина кодового ограничения равна величине порядка К = 10. Попытка повысить эффективность кодирования за счет увеличения длины кодового ограничения вызывает экспоненциальный рост требований к памяти (и сложности), как это следует из уравнения (7.10).

Синхронизация кодовых слов ветвей — это процесс определения начала слова ветви в принятой последовательности. Такую синхронизацию можно осуществить, не при­бавляя новую информацию к потоку передаваемых символов, поскольку можно ви­деть, что, пока принятые данные не синхронизированы, у них непомерно высокая частота появления ошибок. Следовательно, синхронизацию можно осуществить про­сто: нужно проводить сопутствующее наблюдение за уровнем частоты появления ошибок, т.е. нас должна интересовать частота, при которой увеличиваются метрики состояний, или частота, при которой сливаются выжившие пути на решетке. Пара­метр, за которым следят, сравнивается с пороговым значением, после чего соответст­вующим образом осуществляется синхронизация.

7.4. Свойства сверточных кодов

7.4.1. Пространственные характеристики сверточных кодов

Рассмотрим пространственные характеристики сверточных кодов в контексте простого кодера (рис. 7.3) и его решетчатой диаграммы (рис. 7.7). Мы хотим узнать расстояния между всеми возможными парами последовательностей кодовых слов. Как и в случае блочных кодов (см. раздел 6.5.2), нас интересует минимальное расстояние между всеми такими парами последовательностей кодовых слов в коде, поскольку минимальное расстояние связано с возможностями коррекции ошибок кода. Поскольку сверточный код является групповым или линейным [6], можно без потери общности просто найти минимальное расстояние между последовательностью кодовых слов и нулевой после­довательностью. Другими словами, для линейного кода данное контрольное сообще­ние окажется точно таким же “хорошим”, как и любое другое. Так почему бы не взять то сообщение, которое легко проследить, а именно нулевую последователь­ность? Допустим, что на вход передана нулевая последовательность; следовательно, нас интересует такой путь, который начинается и заканчивается в состоянии 00 и не возвращается к состоянию 00 нигде внутри пути. Всякий раз, когда расстояние любых других путей, которые сливаются с состоянием а = 00 в момент t„ окажется меньше расстояния нулевого пути, вплоть до момента г„ будет появляться ошибка, вызывая в процессе декодирования отбрасывание нулевого пути. Иными словами, при нулевой передаче ошибка возникает всегда, когда не выживает нулевой путь. Следовательно, ошибка, о которой идет речь, связана с выживающим путем, который расходится, а затем снова сливается с нулевым путем. Может возникнуть вопрос, зачем нужно, что­бы пути сливались? Не будет ли для обнаружения ошибки достаточно лишь того, что­бы пути расходились? В принципе, достаточно, но если ошибка характеризуется толь­ко расхождением, то декодер, начиная с этой точки, будет выдавать вместо оставшего­ся сообщения сплошной “мусор”. Мы хотим выразить возможности декодера через число обычно появляющихся ошибок, т.е. хотим узнать “самый легкий” для декодера способ сделать ошибку. Минимальное расстояние для такой ошибки можно найти, полностью изучив все пути из состояния 00 в состояние 00. Итак, давайте сначала за­ново начертим решетчатую диаграмму, как показано на рис. 7.16, и обозначим каж­дую ветвь не символом кодового слова, а ее расстоянием Хэмминга от нулевого кодо­вого слова. Расстояние Хэмминга между двумя последовательностями разной длины можно получить путем их сравнивания, т.е. прибавив к началу более короткой после­довательности нужное количество нулей. Рассмотрим все пути, которые расходятся из нулевого пути и затем в какой-то момент снова сливаются в произвольном узле. Из диаграммы на рис. 7.16 можно получить расстояние этих путей до нулевого пути. Итак, на расстоянии 5 от нулевого пути имеется один путь; этот путь отходит от нуле­вого в момент t\ и сливается с ним в момент г₄. Точно так же имеется два пути с рас­стоянием 6, один отходит в момент t_x и сливается в момент г₅, а другой отходит в мо­мент t\ и сливается в момент t₆ и т.д. Также можно видеть (по пунктирным и сплош­ным линиям на диаграмме), что входными битами для расстояния 5 будут 10 0; от нулевой входной последовательности эта последовательность отличается только одним битом. Точно так же входные биты для путей с расстоянием 6 будут 1 1 0 0 и 1010 0; каждая из этих последовательностей отличается от нулевого пути в двух местах. Ми­нимальная длина пути из числа расходящихся, а затем сливающихся путей называется

Гпоdо 7 k'olio п1_игчо лмпгчоэимо’ иягтк 9

минимальным просветом (minimum free distance), или просто просветом (free distance). Его можно видеть на рис. 7.16, где он показан жирной линией. Для оценки возмож­ностей кода коррекции ошибок, мы повторно приведем уравнение (6.44) с заменой минимального расстояния на просвет d/.

d_f-1

ЗдесьUJ означает наибольшее целое, не большее х. Положив d_f = 5, можно видеть, что код, описываемый кодером на рис. 7.3, может исправить две любые ошибки канала (см. раздел 7.4.1.1).

  Рис. 7.16. Решетчатая диаграмма с обозначенными рас­стояниями от нулевого пути

Решетчатая диаграмма представляет собой “правила игры”. Она является как бы символическим описанием всех возможных переходов и соответствующих начальных и конечных состояний, ассоциируемых с конкретным конечным автоматом. Эта диа­грамма позволяет взглянуть глубже на выгоды (эффективность кодирования), которые дает применение кодирования с коррекцией ошибок. Взглянем на рис. 7.16 и на воз­можные ошибочные расхождения и слияния путей. Из рисунка видно, что декодер не может сделать ошибку произвольным образом. Ошибочный путь должен следовать од­ному из возможных переходов. Решетка позволяет нам определить все такие доступ­ные пути. Получив по этому пути кодированные данные, мы можем наложить огра­ничения на переданный сигнал. Если декодер знает об этих ограничениях, то это по­зволяет ему более просто (используя меньшее £,/Л/₀) удовлетворять требованиям надежной безошибочной работы.

Хотя на рис. 7.16 представлен способ прямого вычисления просвета, для него можно получить более строгое аналитическое выражение, воспользовавшись для этого диаграммой состояний, изображенной на рис. 7.5. Для начала обозначим ветви диа­граммы состояний как D°= 1, D¹ или D², как это показано на рис. 7.17, где показатель D означает расстояние Хэмминга между кодовым словом этой ветви и нулевой вет­вью. Петлю в узле а можно убрать, поскольку она не дает никакого вклада в про­странственные характеристики последовательности кодовых слов относительно нуле­вой последовательности. Более того, узел а можно разбить на два узла (обозначим их а и е), один из них представляет вход, а другой — выход диаграммы состояний. Все

7 4 ОВПИГТРЯ ГиРПТЛиииу ь'гтгю
пути, начинающиеся из состояния а = 00 и заканчивающиеся в е = 00, можно просле­дить на модифицированной диаграмме состояний, показанной на рис. 7.17. Переда­точную функцию пути abc е (который начинается и заканчивается в состоянии 00) можно рассчитать через неопределенный “заполнитель” D как ifDD² = D⁵. Степень D — общее число единиц на пути, а значит, расстояние Хэмминга до нулевого пути. Точно так же пути abdc в и abcbce имеют передаточную функцию D⁶ и, соответст­венно, расстояние Хэмминга, равное 6, до нулевого пути. Теперь уравнения состоя­ния можем записать следующим образом:

Дата добавления: 2015-10-28