Пред.
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 След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
ГЛАВА 4 ПРИНЦИПЫ НЕАЛГЕБРАИЧЕСКОГО ДЕКОДИРОВАНИЯ ИЗБЫТОЧНЫХ КОДОВВведениеНеалгебраические методы
декодирования помехоустойчивых кодов появились сразу, как только стало ясно,
что методы декодирования, опирающиеся на строгие нормы алгебраической теории групп,
колец и полей существенно усложняют конструкцию декодера. На начальных этапах
своего становления технология кодирования и декодирования использовала
относительно простые сдвиговые регистры. Обратные связи и сумматоры таких
регистров отражали структуру порождающего полинома
Большинство специалистов по теории помехоустойчивого кодирования считают, что первым устройством, в котором была реализована идея неалгебраического декодирования циклических кодов, был декодер Меггита [65, 74]. Подобная конструкция являлась декодером максимального правдоподобия и рассчитывалась на обработку только жестких решений. Было установлено, что сложность такого декодера с ростом числа исправляемых ошибок растет экспоненциально, поэтому он предназначался для коррекции ошибок небольшой кратности (до трех включительно). Как указывалось выше, для
циклических кодов существует взаимно однозначное соответствие между множеством
всех исправляемых ошибок и множеством всех синдромов. Если Использование
информационных множеств для построения алгоритмов декодирования групповых кодов
было предложено Прейнджем [65, 73]. Информационным множеством группового (n,k) – кода называется любое множество k символов кодового слова, которые
можно задавать независимо. Остальные Шаг 1. Выбрать несколько различных информационных множеств в соответствии с некоторым правилом. Шаг 2. Построить кодовое слово для каждого из множеств, предположив, что символы информационного множества приняты без ошибок. Шаг 3. Сравнить каждое гипотетическое кодовое слово с принятой последовательностью и выбрать ближайшее кодовое слово (находящееся на наименьшем расстоянии). Другим направлением является перестановочное декодирование, которое возможно реализовать как с использованием порождающей матрицы G, так и с помощью проверочной матрицы H [77, 78, 89]. Комбинация ошибок будет определена, если удается найти проверочное множество целиком, содержащее эту комбинацию. Такое проверочное множество называется покрывающим комбинацию ошибок. Набор проверочных множеств, покрывающим комбинацию ошибок данного типа, называется покрытием. Задача декодера состоит в том, чтобы найти проверочное множество, которое покрывает данную неизвестную комбинацию ошибок. При использовании заранее выбранного покрывающего множества возникает два важных вопроса. Первый из них состоит в том, каково минимальное число различных проверочных множеств, необходимых для исправления данного числа ошибок, второй – как найти эти множества. Ни на один из этих вопросов нет вполне удовлетворительного ответа. Благодаря усилиям отечественных авторов: В.В. Золотареву, Г.В. Овечкину и др., активно развивается концепция многопорогового декодирования, берущая свое начало от порогового декодирования Меггита [54, 55]. Такой метод декодирования применим не только к групповым кодам, но и к непрерывным кодам, однако этот метод целесообразно применять к кодам определенной структуры: к мажоритарно декодируемым кодам или к самоортоганальным кодам. Сложность порогового декодера пропорциональна кодовому расстоянию, следовательно, быстрое увеличение этого параметра оказывается малоэффективным. Кроме того, при фиксированном значении кодового расстояния лучшими энергетическими характеристиками обладать коды с большей кодовой скоростью. Многопороговый декодер
самоортоганальных кодов является развитием простейшего порогового декодера и
позволяет декодировать очень длинные коды с линейной от длины кода сложностью
исполнения. Важно отметить, что в основе такого устройства лежит принцип
итеративного приближения к окончательному выбору решения о принятом векторе.
Основной шаг декодирования заключается в том, что для произвольного взятого
символа uj вычисляется функция правдоподобия Lj , от относящихся к нему проверок Подобная ситуация активизировала поиски иных подходов к процедуре декодирования помехоустойчивых кодов. Одним из таких направлений явилось списочное декодирование. Именно к таким методам следует отнести, прежде всего, приемы списочного декодирования, которые были введены Элайесом и Возенкрафтом [40, 59, 65, 74]. Алгоритм списочного декодирования имеет самостоятельное значение при решении различных задач. Списочный декодер вместо единственного решения выдает получателю список предполагаемых решений о передаваемом сообщении. Ошибкой является такой результат декодирования, когда в списке нет правильного сообщения. Понятно, что вероятность ошибки такого списочного декодера много меньше вероятности ошибки обычного декодера. Наиболее очевидное применение этого подхода возможно в системах с каскадным кодированием. Результатом декодирования внутреннего кода является список решений, а декодер внешнего кода устраняет оставшуюся неопределенность. Алгоритм декодирования, основанный на списках, обеспечивает лучшее соотношение между сложностью и вероятностью ошибки, чем другие известные алгоритмы. Это справедливо в асимптотике при увеличении кодового ограничения кода, а также при использовании конкретных конструкций кодов конечной длины. Научный поиск в области построения эффективных избыточных кодов и каскадных конструкций на их основе продолжается. Развитие технологии реализации устройств кодирования и декодирования на базе интегральных микросхем и сигнальных процессоров существенно расширяет круг технически реализуемых решений. Этим стимулируется интерес к исследованиям в данной области. Списочное
декодирование
|
1 |
Оглавление
|