www.chms.ru - вывоз мусора в Балашихе 

Динамо-машины  Сигналы и спектры 

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

разрядов являются конечным состоянием для такого перехода. Последовательность кодовых символов характеризуется Л ветвями (что представляет Л бит данных), занимающими N интервалов времени. Она связана с конкретным состоянием в каждый из N +1 интервалов времени (от начала до конца). Таким образом, мы запускаем биты в моменты времени г Гг, ts и интересуемся метрикой состояния в моменты времени ?1, t2, tfi+i- Здесь использовано следующее условие: текущий бит располагается в крайнем левом разряде, а крайние правые К - 1 разрядов стартуют из состояния со всеми нулями. Этот момент времени обозначим как начальное время, Время завер-щения последнего перехода обозначим как время прекращения работы, Глг+i-

7.3. Формулировка задачи сверточного кодирования

7.3.1. Декодирование по методу максимального правдоподобия

Если все входные последовательности сообщений равновероятны, минимальная вероятность ошибки получается при использовании декодера, который сравнивает условные вероятности и выбирает максимальную. Условные вероятности также называют функциями правдоподобия Р(Х\\У- ), где Z - это принятая последовательность, а U * - одна из возможных переданных последовательностей. Декодер выбирает I/ *, если

PCZIU *) = max PiZp )

по всеми raquo;.

Принцип максимального правдоподобия, определяемый уравнением (7.1), является фундаментальным достижением теории принятия решений (см. приложение Б); это формализация способа принятия решений, основанного на здравом смысле , когда имеются статистические данные о вероятностях. При рассмотрении двоичной демодуляции в главах 3 и 4, предполагалась передача только двух равновероятных сигналов ii(0 и *2(0- Следовательно, принятие двоичного решения на основе принципа максимального правдоподобия, касающееся данного полученного сигнала, означает, что в качестве переданного сигнала выбирается si(t), если

p{z\si) gt;p{z\s2).

В противном случае считается, что передан был сигнал зО- Параметр г представляет собой величину г(7), значение принятого сигнала до детектирования в конце каждого периода передачи символа t = T. Однако при использовании принципа максимального правдоподобия в задаче сверточного декодирования, в сверточном коде обнаруживается наличие памяти (полученная последовательность является суперпозицией текущих и предьщущих двоичных разрядов). Таким образом, применение принципа максимального правдоподобия при декодировании бит данных, закодированных сверточным кодом, осуществляется в контексте выбора наиболее вероятной последовательности, как показано в уравнении (7.1). Обычно имеется множество возможных переданных последовательностей кодовых слов. Что касается двоичного кода, то последовательность из L кодовых слов является членом набора из 2- возможных последовательностей. Следовательно, в контексте максимального правдоподобия можно сказать, что в качестве переданной последовательности декодер выбирает Ц* , если правдоподобие PCZIU* *) больше правдоподобия всех остальньк возможно переданных последовательностей. Та-



кой оптамальный декодер, минимизирующий вероятность ошибки (когда все переданные последовательности равновероятны), известен как декодер, работающий по принципу максимального правдоподобия (maximum likelihood detector). Функция правдоподобия задается или вычисляется, исходя из спецификации канала.

Предположим, что мы имеем дело с аддитивным белым гауссовым шумом с нулевым средним, следовательно, каналом без памяти, т.е. шум влияет на каждый символ кода независимо от остальных символов. При степени кодирования сверточного кода, равной 1/п, правдоподобие можно выразить следующим образом:

оо П

Здесь Zi - это i-я ветвь принятой последовательности Z, i * - это ветвь отдельной последовательности кодовых слов и* , Zji - это у-й кодовый символ Zi, laquo;,/ - это у-й кодовый символ i *, а каждая ветвь состоит из п кодовых символов. Задача декодирования заключается в выборе пути сквозь решетку, показанную на рис. 7.7 (каждый возможный путь определяет последовательность кодовых слов), таким образом, чтобы произведение

оо П

ПП J максимальным. (7.3)

i=i у=1

Как правило, при вычислениях удобнее пользоваться логарифмом функции правдоподобия, поскольку это позволяет произведение заменить суммированием. Мы можем воспользоваться таким преобразованием, поскольку логарифм является монотонно возрастающей функцией и, следовательно, не внесет изменений в выбор окончательного кодового слова. Логарифмическую функцию правдоподобия можно определить следующим образом:

у vim) = Ig P(Z1U lt; ) = Ig P(Z,.lt gt;) = XZg PijiWT) (7-4)

1=1 1=1;=i

Теперь задача декодирования заключается в выборе пути вдоль дерева на рис. 7.6 или решетки на рис. 7.7 таким образом, чтобы Уи( ) было максимальным. При декодировании сверточных кодов можно использовать как древовидную, так и решетчатую структуру. При древовидном представлении кода игнорируется то, что пути снова объединяются. Для двоичного кода количество возможных последовательностей, состоящих из L кодовых слов, равно I -. Поэтому декодирование полученных последовательностей, основанное на принципе максимального правдоподобия с использованием древовидной диаграммы, требует метода фубой силы или исчерпывающего сопоставления 2 накопленных логарифмических метрик правдоподобия, описывающих все варианты возможных последовательностей кодовых слов. Поэтому рассматривать декодирование на основе принципа максимального правдоподобия с помощью древовидной структуры практически невозможно. В предьщущем разделе было показано, что при решетчатом представлении кода декодер можно построить так, чтобы можно было отказываться от путей, которые не могут быть кандидатами на роль максимально правдоподобной последовательности. Путь декодирования выбирается из некоего сокращенного набора выживших путей. Такой деко-



дер тем не менее является оптимальным; в том смысле, что путь декодирования такой же, как и путь, полученный с помощью декодера критерия максимального правдоподобия, действующего грубой силой , однако предварительный отказ от неудачных путей снижает сложность декодирования.

В качестве великолепного пособия для изучения структуры сверточных кодов, декодирования на основе критерия максимального правдоподобия и реализации кода можно порекомендовать работу [8]. Существует несколько алгоритмов, которые дают приблизительные решения задачи декодирования на основе критерия максимального правдоподобия, включая последовательный [9, 10] и пороговый [И], Каждый из этих алгоритмов является подходящим для узкоспециальных задач; однако все они близки к оптимальному. Алгоритм декодирования Витерби, напротив, осуществляет декодирование на основе критерия максимального правдоподобия шире, следовательно, является оптимальным. Это не означает, что алгоритм Витерби в любой реализации является наилучшим; при его использовании существуют жесткие условия, налагаемые на аппаратное обеспечение. Алгоритм Витерби обсуждается в разделах 7.3.3. и 7.3.4.

7.3.2. Модели каналов: мягкое или жесткое принятие решений

Перед тем как начать разговор об алгоритме, который задает схему принятия максимально правдоподобного решения, давайте сначала опишем канал. Последовательность кодовых слов и* , определяемую словами ветви, каждое из которых состоит из и кодовых символов, можно рассматривать как бесконечный поток, в отличие от блочного кода, где исходные данные и их кодовые слова делятся на блоки строго определенного размера. Последовательность кодовых слов, показанная на рис. 7.1, вьща-ется сверточным кодером и подается на модулятор, где кодовые символы преобразуются в сигналы. Модуляция может быть низкочастотной (например, модуляция импульсными сигналами) или полосовой (например, модуляция PSK или FSK). Вообще, за такт в сигнал si) преобразуется I символов, где / - целое, причем / = 1, 2, а М = 2. Если Z = 1, модулятор преобразует каждый кодовый символ в двоичный сигнал. Предполагается, что канал, по которому передается сигнал, искажает сигнал гауссовым шумом. После того как искаженный сигнал принят, он сначала обрабатывается демодулятором, а затем подается на декодер.

Рассмотрим ситуацию, когда двоичный сигнал передается за отрезок времени (О, Т), причем двоичная единица представляется сигналом 5,(0, а двоичный нуль - сигналом 52(0- Принятый сигнал имеет вид lif) = s,(f) + n(f), где n(f) представляет собой вклад гауссового шума с нулевым средним. В главе З мы описывали детектирование r(f) в два основных этапа. На первом этапе принятый сигнал переводится в число г(Г) = о, + По, где а, - это компонент сигнала г(Г), а ио - компонент шума. Компонент шума По - это случайная переменная, значения которой имеют гауссово распределение с нулевым средним. Следовательно, г(Г) также будет случайной гауссовой величиной со средним Oi или ai, в зависимости от того, какая величина была отправлена - двоичная единица или двоичный нуль. На втором этапе процесса детектирования принимается решение о том, какой сигнал был передан. Это решение принимается на основе сравнения zij) с порогом. Условные вероятности г(Г), p(z\s\) и рЦг), показанные на рис. 7.8, обозначены как правдоподобие s\ и si. Демодулятор, представленный на рис. 7.1, преобразует упорядоченный по времени набор случайных переменных {г(Г)} в кодовую последовательность Z и подает ее на декодер. Выход демодулятора можно



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