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

16. Декодер уходит с этого пути, и счетчик переустанавливается на 2. На этом уровне ?5 все альтернативные пути использованы, поэтому декодер возвращается на узел в момент Г4 и переустанавливает счетчик на 1.

17. Декодер пробует альтернативный путь в узле /4, метрика которого возрастает до 3, поскольку в кодовом слове имеется несовпадение в двух позициях. В этот момент декодер должен сделать откат всех путей до момента ?2, поскольку все пути более высоких уровней уже использованы. Счетчик снова переустановлен на нуль.

18. В узле ?2 декодер следует кодовому слову 01. Поскольку имеется несовпадение в одной позиции с принятыми в момент ?2 кодовыми символами 00, то счетчик устанавливается на 1.

Далее декодер продолжает свои поиски таким же образом. Как видно из рис. 7.23, финальный путь, счетчик которого не нарушает критерия точки возврата, дает правильно декодированную информационную последовательность 110 11. Последовательное декодирование можно понимать как тактику проб и ошибок для поиска правильного пути на кодовом дереве. Поиск осуществляется последовательно; всегда рассматривается только один путь за раз. Если принимается неправильное решение, последующие пути будут ошибочными. Декодер может со временем распознать ошибку, отслеживая метрики пути. Алгоритм напоминает путешественника, отыскивающего путь на карте дорог. До тех пор, пока путешественник видит, что дорожные ориентиры соответствуют таковым на карте, он продолжает путь. Когда он замечает странные ориентиры (увеличение его своеобразной метрики), в конце концов приходит к выводу, что он находится на неправильном пути, и возвращается к точке, где он может узнать ориентиры (его метрика возвращается в приемлемые рамки). Тогда он пробует альтернативный путь.

7.5.2. Сравнение декодирования по алгоритму Витерби

с последовательным декодированием и их ограничения

Главный недостаток декодирования по алгоритму Витерби заключается в том, что в то время, как вероятность появления ошибки экспоненциально убывает с ростом длины кодового Офаничения, число кодовых состояний, а значит сложность декодера, экспоненциально растет с увеличением длины кодового ограничения. С другой стороны, вычислительная сложность алгоритма Витерби является независимой от характеристики канала (в отличие от жесткого и мягкого декодирования, которые требуют обычного увеличения объемов вычислений). Последовательное декодирование асимптотически достигает той же вероятности появления ошибки, что и декодирование по принципу максимального правдоподобия, но без поиска всех возможных состояний. Фактически при последовательном декодировании число перебираемых состояний существенно независимо от длины кодового ограничения, и это позволяет использовать очень большие (К = 41) длины кодового Офаничения. Это является важным фактором при обеспечении таких низких вероятностей появления ошибок. Основным недостатком последовательного декодирования является то, что количество перебираемых метрик состояний является случайной величиной. Для последовательного декодирования ожидаемое число неудачных гипотез и повторных переборов является функцией канального отношения сигнал/шум (signal to noise ratio - SNR). При низком SNR приходится перебирать больше гипотез, чем при высоком SNR. Из-за такой изменчивости вычислительной нафузки, поступившие последовательности необходимо сохранять в буфере памяти. При низком SNR последовательности поступают в буфер до тех пор, пока декодер не сможет найти



7.6. Резюме

в течение последних десяти лет наиболее популярной схемой кодирования являлась сверточная, поскольку почти во всех приложениях сверточные коды лучше блочных при той же конструктивной сложности кодера и декодера. Для каналов спутниковой связи схемы прямого исправления ошибок позволяют легко понизить на 5-6 дБ требуемое значение SNR для заданной достоверности передачи. Из этой эффективности кодирования непосредственно вытекает снижение эффективной изотропной излучаемой мощности спутника (effective isotropic radiated power - EIRP), что, соответственно, приводит к снижению веса и стоимости спутника.

В этой главе мы описали значительную структурную разницу между блочными и сверточными кодами - сверточные коды со степенью кодирования Ifn сохраняют в памяти предьщущие К-1 бит, где К означает длину кодового офаничения. С такой памятью кодирование каждого входного бита данных зависит не только от значения этого бита, но и от предшествующих ему К-1 бит. Задача описывалась в контексте алгоритма максимального правдоподобия. При его использовании изучаются все возможные последовательности кодовых слов, которые могли быть созданы кодером, и выбирается та, которая выглядит статистически наиболее вероятной. Решение опирается на метрику расстояния принятых кодовых символов. Анализ безошибочной работы сверточных кодов является более сложным, чем простое биномиальное разложение, описывающее работу без ошибок многих блочных кодов. Здесь также введено понятие просвета и указана связь между просветом и границами надежной работы. Кроме того, в этой главе описаны основные идеи, касающиеся последовательного декодирования и декодирования с обратной связью, а также приведены некоторые сравнительные характеристики и таблицы различных схем кодирования.

Литература

1. GallagerR. G. Information Theory and Reliable Communication. John Wiley amp; Sons, Inc., New York, 1968.

2. Fano R. M. A Heuristic Discussion of Probabilistic Decoding. IRE Trans. Inf. Theory, vol. IT9. n. 2, 1963, pp. 64-74.

3. Odenwalder J. P. Optimal Decoding of Convolutional Codes. Ph. D. dissertation. University of California, Los Angeles, 1970.

4. Curry S. J. Selection of Convolutional Codes Having Large Free Distance. Ph. D. dissertation. University of California, Los Angeles, 1971.

5. Larsen K. J. Short Conolutional Codes with Maximal Free Distance for Rates 1/2, 1/3, and 1/4. IEEE Trans. Inf Theory, vol. IT19, n. 3, 1973, pp. 371-372.

6. Lin S. and Costello D. J. Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Inc., Englewood Cliffs, N. J., 1983.

7. Forney G. D. Jr. Convolutional Codes: I. Algebraic Structure. IEEE Trans. Inf Theory, vol. IT16, n. 6, November, 1970, pp. 720-738.

8. Viterbi A. Convolutional Codes and Their Рефгтапсе in Communication Systems. IEEE Trans. Commun. Technol., vol. C0M19, n. 5, October, 1971, pp. 751-772.

9. Forney G. D. Jr. and Bower E. K. A High Speed Sequential Decoder: Prototype Design and Test IEEE Trans. Commun. Technol., vol. C0M19, n. 5, October, 1971, pp. 821-835.

10. Jelinek F. Fast Sequential Decoding Algorithm Using a Stack. IBM J. Res. Dev., vol.13, November, 1969, pp. 675-685.

11. Massey J. L. Threshold Decoding The MIT Press, Cambridge, Mass., 1963.



7.5.3. Декодирование с обратной связью

Декодер с обратной связью реализует жесткую схему принятия решений относительно информационного бита в разряде j, исходя при этом из метрик, полученных из разрядов j, j + 1, j + га, где га - заранее установленное положительное целое число. Длина упреждения (look-ahead length) L определяется как L = m+\, количество принятых кодовых символов, выраженных через соответствующее число входных битов, задействованных для декодирования информационного бита. Решение о том, является ли информационный бит нулем или единицей, принимается в зависимости от того, на какой ветви путь минимального расстояния Хэмминга переходит в окне упреждения (look-ahead window) из разряда j в разряд У + га. Поясним это на конкретном примере. Рассмотрим декодер с обратной связью, предназначенный для сверточного кода со степенью кодирования 1/2, который показан на рис. 7.3. На рис. 7.25 приведена древовидная диаграмма и работа декодера с обратной связью при L = 3. Иными словами, при декодировании бита из ветви j декодер содержит пути из ветвей j, j+ \ nj +2.

Начиная из первой ветви, декодер вычисляет 2 (восемь) совокупных метрик путей расстояния Хэмминга и решает, что бит для первой ветви является нулевым, если путь минимального расстояния содержится в верхней части дерева, и единичным, если путь минимального расстояния находится в нижней части дерева. Пусть принята последовательность Z = l 10001000 1. Рассмотрим восемь путей от момента ?, до момента fj в блоке, обозначенном на рис. 7.24 буквой А, и рассчитаем метрики, сравнивая эти восемь путей для первых шести принятых кодовых символов (три ветви вглубь умножить на два символа для ветви). Выписав метрики Хэмминга общих путей (начиная с верхнего пути), видим, что они имеют следующие значения:

метрики верхней части 3, 3, 6, 4

метрики нижней части 2,2, 1,3

Видим, что наименьшая метрика содержится в нижней части дерева. Следовательно, первый декодированный бит является единицей (и определяется сдвигом вниз на дереве). Следующий шаг будет состоять в расширении нижней части дерева (выживающий путь) на один разряд глубже, и здесь снова вычисляется восемь метрик, теперь уже для моментов t2-ti. Получив, таким образом, два декодированных символа, мы теперь можем сдвинуться на два символа вправо и снова начать расчет метрик путей, но уже для шести кодовых символов. Эта процедура видна в блоке, обозначенном на рис. 7.25 буквой В. И снова, проследив метрики верхних и нижних путей, находим следующее:

метрики верхней части 2, 4, 3, 3

метрики нижней части 3, 1, 4, 4

Минимальная метрика дпя ожидаемой принятой последовательности находится в нижней части блока В. Следовательно, второй декодируемый бит также является единицей.

Таким образом, процедура продолжается до тех пор, пока не будет декодировано все сообщение целиком. Декодер называется декодером с обратной связью, поскольку найденное решение подается обратно в декодер, чтобы потом использовать его в определении подмножества кодовых путей, которые будут рассматриваться следующими. В канале BSC декодер с обратной связью может оказаться почти таким же эффективным, как и декодер, работающий по алгоритму Витерби [17]. Кроме того, он может исправлять все наиболее вероятные модели ошибки, а именно - те, которые имеют весовой коэффициент (t - 1)/2 или менее, где df - просвет кода. Важным параметром



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