Главная Помехоустойчивое кодирование



помехоустойчивое кодирование

Одна из наиболее важных и одновременно трудных задач в технике передачи, записи, воспроизведения и хранения информации - обеспечение помехоустойчивости. Теоретическое решение этой задачи было найдено в 40-е годы К, Шенноном. Он не только связал достоверность и скорость передачи информации с пропускной способностью канала связи, но и указал путь надежной передачи данных за счет введения избыточности при кодировании сообщений, т. е. до их передачи в канал или записи на носитель. Так, в середине нашего века зародилась и стала бурно развиваться теория помехоустойчивого кодирования - эффективное средство по обеспечению контроля (обнаружения и исправления) ошибок.

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

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

Цель данной книги - ознакомить инженера-разработчика с основами математического аппарата, необходимого для создания помехоустой-



чивой аппаратуры телепередачи, записи и считывания дискретной информации, и в конечном счете способствовать сокращению разрыва между теорией и практикой. Для удобства читателя, впервые знакомящегося с разделами конечной алгебры, использован следующий методический прием. Основы помехоустойчивого кодирования, дискретные ортогональные преобразования, аппроксимация Паде, а также теория ганке-левых и теплицевых матриц первоначально излагаются применительно к рациональным, вещественным или комплексным числам с обычными "школьными" операциями над ними, а уже затем рассматриваются в конечных алгебрах с учетом специфики алгебраических операций.

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



ГЛАВА ПЕРВАЯ

ВВЕДЕНИЕ В ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

1.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Дискретные сообщения и видь! их искажений. Предположим, что задано сообщение {d, Q2, •••) , образованное последовательностью символов выбираемых из некоторого конечного алфавита К. Такие сообщения называются дискретными.

Как правило, "буквами" алфавита К являются наборы длины г из элементов множества Р = 0, 1, ... , р - 1} , где р> 1, р - простое число (объяснение, почему р - простое число, дано ниже). Количество q таких наборов равно . Следовательно, мощность множества К, т.е. число его элементов, обозначаемое \К\ также равно q ид = рг.

Чаще всего принимают р ~ 2, т. е. используют двоичные наборы из элементов О и 1; эти наборы Moryi быть пронумерованы: О, 1, . .. , где "ЗВ = q ~ \ ; q - 2 - количество двоичных наборов. Таким образом, символы Qj дискретного сообщения выбираются из алфавита К -

= (о, 1,...,ае} .

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

Ошибки в некоторых каналах имеют тенденцию группироваться. Последовательность v искаженных символов, первый и последний символ которой не равны нулю, называется пакетом ошибок длины

Обеспечение помехоустойчивости телепередачи за счет иэбьпч>чности. Как показал К. Шеннон [49], помехоустойчивость передачи сообщения на расстояние может быть обеспечена за счет избыточности. Интуитивно ясно, что если продублировать символ Q, составив кодовую посылку С (2> то можно выявить одну ошибку. Однако при дублировании локализовать ошибку, т. е. установить ее место, не удается, а потому возможно лишь обнаружение, но не исправление ошибки. Для исправления (выявления и локализации) ошибки символ Q должен быть по крайней мере повторен трижды: (2, Q, Q, для исправления двух ошибок - повторен пять раз и т. д. Для исправления v ошибок символ повторяется W = 2у+ 1 раз. В зтом случае, если количество ошибок не превышает



[0] 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


0.0182