Пред.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
7. ДРУГИЕ МЕТОДЫ ДЕКОДИРОВАНИЯ СВЕРТОЧНЫХ КОДОВМетоды сверточного кодирования исследовались в течение многих лет. Сверточные коды были впервые введены Элайсом [63] в 1955 г. Вскоре после этого Возенкрафт [64] разработал метод, который он назвал последовательным декодированием. Этот метод активно изучался в течение более чем 20 лет. Он представляет собой декодирование путем проб и ошибок, и его характеристики иногда достигают или даже превосходят характеристики декодеров Витерби. Поэтому в некоторых практических случаях такой метод оказывается более предпочтительным. Одно из основных свойств последовательного декодирования состоит в том, что время, требуемое для декодирования данного информационного символа, является случайной величиной. В этом отношении алгоритм последовательного декодирования очень похож на методы случайного поиска при декодировании блоковых кодов, обсуждавшиеся в гл. 3. В первые годы исследования сверточных кодов стало ясно, что, хотя последовательное декодирование приводит к значительному улучшению характеристик, его реализация в то время представлялась очень дорогой. Поэтому некоторые исследователи пытались найти субоптимальные алгоритмы декодирования сверточных кодов, реализация которых была бы более простой. В отличие от последовательного декодирования найденные методы были детерминированными, так что при одном цикле вычислений производилось полное декодирование одного кодового ребра. Обычно такие методы основаны на вычислении синдромной последовательности, которая зависит только от ошибок в канале. Аналогично тому, как в блоковых кодах, синдром определяет систему линейных уравнений, и нужно найти решение этой системы, имеющее минимальный вес. Поправки для принятых информационных символов формируются как подходящие функции от символов синдрома. Поэтому подобные методы будем называть методами синдромного декодирования. Одним из широко используемых методов синдромного декодирования является декодирование путем табличного поиска с обратной связью. Как следует из названия, формирование поправочных символов по символам синдрома осуществляется путем поиска в таблице (которая может храниться в постоянной памяти). Этот метод очень похож на детектирование Меггитта для блоковых кодов, рассмотренное в гл. 3. Другим широко используемым методом синдромного декодирования является пороговое декодирование. Алгоритмы порогового декодирования, используемые для жесткого или мягкого решения, по существу, совпадают с соответствующими алгоритмами декодирования блоковых кодов, обсуждавшимися соответственно в гл. 3 и 4. Был найден широкий класс сверточных кодов, допускающих пороговое декодирование. 7.1. Методы синдромного декодированияДва наиболее часто используемых метода синдромного декодирования: декодирование путем табличного поиска и пороговое декодирование — преобразовывают символы синдрома в требуемые поправочные символы. Основное различие между этими методами состоит в том, что при табличном поиске в декодере обычно реализуется оптимальное преобразование, позволяющее получить хорошие характеристики даже при коротких синдромных последовательностях. Поскольку синдромныь последовательности обязательно должны быть короткими (для облегчения реализации), важно оптимизировать используемый код. При пороговом декодировании реализуются некоторые специальные преобразования, допускающие существенно более длинные синдромные последовательности, однако такое декодирование возможно лишь для кодов с весьма специальными свойствами. К сожалению, допустимые коды оказываются сравнительно плохими, так что получаемый выигрыш от кодирования оказывается небольшим. Далее будут рассматриваться только систематические коды. Позднее будет показано, что несистематические коды обладают лишь незначительными преимуществами и поэтому почти никогда не применяются в синдромных декодерах. 7.1.1 Основные понятияПрежде чем перейти к обсуждению декодирования путем табличного поиска с обратной связью и порогового декодирования, полезно исследовать некоторые основные понятия и свойства, характерные для обоих методов. Они включают такие структурные свойства, как кодовое расстояние, связь между синдромной последовательностью и последовательностью ошибок в канале, а также структуру декодера. Будут обсуждаться также методы анализа характеристик декодера. Наконец, будет исследоваться проблема неограниченного распространения ошибок в декодерах с обратной связью. Важные понятия будут поясняться на примере кода с 7.1.1.1. Структурные свойства. Используя полиномиальное представление из гл. 6, выходную последовательность систематического кодера с
где
При рассматриваемых методах декодирования для декодирования данного информационного символа информационного символа Для лучшего понимания процесса декодирования с обратной связью рассмотрим систематический код с Данный алгоритм, по существу, совпадает с алгоритмом, применяемым при декодировании путем табличного поиска с обратной связью. Рассмотрим, например, принятую последовательность
Рис. 7.1. Кодовое дерево для систематического кода с декодера относительно первого информационного символа будет Аналогичное декодирование можно осуществить, используя принятый синдром для получения оценки
Используя формулы (7.2) — (7.4), можно выразить синдром как функцию последовательности ошибок в канале, т. е. как функцию от
Оценка информационной последовательности, производимая декодером, имеет вид
Декодирование оказывается правильным в том случае, когда оценка последовательности ошибок совпадает с истинной последовательностью ошибок. Символы синдрома связаны с символами канала равенством (7.6). Для заданного набора В рассмотренном примере кода с
Символ синдрома, соответствующий
Метод исправления ошибок определяется преобразованием, переводящим последовательность символов синдрома в корректирующий символ при наличии одиночной ошибки в
в то время как при появлении одиночной ошибки в
Поскольку два указанных типа одиночных ошибок приводят к различным синдромам, то все одиночные ошибки могут быть исправлены. Алгоритм исправления ошибок состоит в том, чтобы принять Схема кодера, цифрового канала и декодера с обратной связью для этого кода показана на рис. 7.2. Заметим, что обратная связь служит для устранения влияния предыдущих ошибок на синдром. При порождении
если
Это правило эквивалентно правилу декодирования, указанному в предыдущем абзаце. Декодирование согласно такому правилу позволяет исправлять все одиночные ошибки. Коды с большей корректирующей способностью требуют использования последовательностей синдрома, имеющих большую длину, поэтому для их
Рис. 7.2. Кодер и декодер с обратной связью для кода с реализации требуется существенно более сложное решающее устройство. Такие коды будут вскоре рассмотрены. Оказывается, что рассматриваемый код можно декодировать с помощью детерминированного декодера, который по-прежнему будет исправлять все одиночные ошибки. Этот декодер аналогичен декодеру, изображенному на рис. 7.2, за тем исключением, что в нем отсутствует обратная связь. Удаление линии обратной связи, подающей
Из формулы (7.10) видно, что при наличии только одной ошибки в Корректирующие символы для декодирования с обратной связью и для детерминированного декодирования, задаваемые соответственно формулами (7.9) и (7.10), показывают важное различие между этими двумя подходами. В предположении, что декодер с обратной связью не вносил ошибок при декодировании предыдущих символов, получаем, что корректирующий символ зависит только от ошибок в последовательности, покрывающей Определение. Кодовое расстояние при декодировании с обратной связью для двоичного сверточного кода с Заметим, что кодовое расстояние определяется как функция Определение. Кодовое расстояние при детерминированном декодировании, обозначаемое число позиций на длине кодового ограничения (при детерминированном декодировании), в которых различаются две кодовые последовательности с разными значениями При нахождении кодового расстояния при декодировании с обратной связью нужно сравнивать последовательности с одинаковыми
Соответствующие корректирующие способности при этих двух подходах выражаются формулами
7.1.1.2. Анализ характеристик. Характеристики рассчитываются путем суммирования вероятностей всех событий, приводящих к ошибкам. Это легко проиллюстрировать на примере кода с
Вероятность ошибки символа можно вычислить исходя из (7.10) и (1.14). Если
Вычисление вероятности ошибки символа при декодировании с обратной связью оказывается более сложным. Рассмотрим случай совершенной обратной связи. Будем считать, что некоторое «волшебное» устройство обеспечивает подачу по линии обратной связи корректирующего символа, совпадающего с ошибкой в канале. Это устраняет возможность распространения ошибок. Однако никакого другого влияния такое волшебное устройство на работу декодера не оказывает. Тогда для декодера с обратной связью при наличии такого помощника получаем следующий корректирующий символ:
(поскольку считаем, что влияние предыдущих ошибок полностью исключено). Используя (7.16), вероятность ошибки символа можно определить точно так же, как и ранее. При
Поскольку наличие помощника дает точное значение начальной вершины при декодировании каждого символа, то
Важность понятия декодирования с помощником состоит в том, что вероятность первой ошибки декодирования в точности совпадает с
Общая вероятность ошибки символа при декодировании с обратной связью больше
При декодировании более длинных кодов либо с помощью табличного поиска, либо методом порогового декодирования можно применить такие же способы подсчета ошибок для определения Заметим, что при больших значениях отношения сигнал-шум Вообще говоря,
Если обратная связь не приводит к бесконечному распространению ошибок и если 7.1.1.3. Распространение ошибок. Процесс распространения ошибок в сверточных кодах интенсивно исследовался в научной литературе. Имеется несколько типов распространения ошибок, каждый из которых вызывается своими причинами. Распространение ошибок может быть либо ограниченным, либо неограниченным. Ограниченное распространение ошибок в декодерах с обратной связью нельзя полностью устранить. Оно приводит к тому, что Неограниченное распространение ошибок первого типа вызывается плохим выбором кода. Плохие — это так называемые коды с катастрофическим распространением ошибок (см. гл. 6). Месси и Сайн [60] определили свойства порождающего многочлена кода, которые вызывают такой эффект. Заметим, что такие коды обладают плохими свойствами независимо от метода их декодирования. При использовании систематических кодов такой эффект никогда не возникает (все информационные последовательности бесконечного веса приводят к кодовым последовательностям бесконечного веса). Однако даже при хорошем выборе кода декодирование с помощью плохого декодера может вызвать неограниченное распространение ошибок второго типа (в результате появления конечного числа ошибок в канале декодер может внести бесконечное число ошибок в информационные символы). Было пока зано, что при декодировании путем табличного поиска с обратной связью такой эффект возникает в случаях, когда глубина декодирования Для кода с Предположим, что глубина декодирования для кода с
а другой — в том, чтобы вообще не производить исправления, т. е. положить
Автономные схемы состояний для этих двух случаев и для случая
Рис. 7.3. Автономные схемы переходов между состояниями регистра синдрома для нескольких декодеров кода с появляется неправильный член обратной связи, в результате которого регистр синдрома оказывается запертым в состоянии 1, что приводит к неограниченному распространению ошибок второго типа. Во избежание неограниченного распространения ошибок всегда должен существовать путь из любого ненулевого состояния в состояние 0. Ситуация, иллюстрируемая на рис. 7.3, б, оказывается более хорошей, и распространения ошибок не происходит. Однако причина этого в том, что вообще не производится исправления ошибок. Таким образом, вероятность ошибки на выходе декодера равна вероятности ошибки в канале и на неиспользуемые проверочные символы тратятся дополнительные Наконец, правильно построенный декодер с Другим часто используемым является несистематический код с В некоторых работах были получены границы для значения
|
1 |
Оглавление
|