У. Питерсон - Коды, исправляющие ошибки (1267328), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Напротив, для древовидных кодов операции последовательного декодирования представляют собой сильно зависимые события даже для канала без памяти. В этом случае па каждом этапе при декодировании исследуются (гн — 1)л символов, использованных при декодировании предыдущего слова. Таким образом, если известно, что предыдушее слово было деко. дировано неправильно, то вероятность того, что рассматриваемое и во будет также неправильно декодировано, значительно больше, „ем если бы относительно предыдущего слова ничего не было известно. В большинстве практических ситуаций невозможно вычислить условную вероятность правильного декодирования прн условии, что известны результаты всех предыдущих операций декодирования для этого пришлось бы рассматривать слишком много различных случаев, Поэтому обычно вычисляют вероятность правильного первого декодирования, т.

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

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

Таким образом, тремя основными аспектами проблемы кодирования являются: 1) построение кодов, способных в должной мере исправлять ошибки (для этого обычно требуется, чтобы коды были длинными); 2) разработка практически осуществимого метода кодирования; 3) отыскание метода принятия решения на приемнике, т. е. метода исправления ошибок.

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

Замечаиия Хот отя главная цель книги — исследовать коды, исправляющие ошибки, в бок, включа , в ней рассматриваются также задачи обнаружения ошиления оши лючая комбинированную задачу обнаружения и исправошибок, Способность кода обнаруживать ошибки тесно связана с его способностью исправлять ошибки, поэтому естественно рассматривать одновременно оба эти вопроса.

Почти все современное оборудование основано на использовании двоичной системы счисления, н, следовательно, сейчас двоичные коды являются наиболее важными, Почти всегда с незначительными изменениями в формулировках, выводах и доказательствах двоичные коды могут быть обобщены на случай д символов, где д — некоторая степень простого числа. Этот более общий случай очень важен. Во-первых„недвоичные коды могут использоваться в том случае, когда информация поступает в недвоичной записи. Например, информация в десятичной записи может быть достаточно эффективно представлена кодом с д = 11. Во-вторых, новые двоичные коды можно строить на основе недвоичных кодов, особенно тех, для которых д является степенью 2.

Общий случай недвоичных кодов рассматривается в этой книге всюду, где это не загромождает изложения. Читатель, который интересуется только двоичными кодами, может прн чтении просто заменять д на 2 и слова «элемент поля» на «двоичный символь. В этой книге используется расстояние Хэмминга П38]; однако существует по крайней мере еще одно расстояние: расстояние Ли 120, 180, 245, 3091, которое использовалось в теории кодирования.

Расстояние Ли и расстояние Хэмминга совпадают в двоичном случае и прн 4=3. В этой книге главным образом рассматриваются коды, алгебраические по своей основной структуре. Большая часть работ по теории кодирования относится к этой области. Кроме того, рассматриваются также коды, связанные с другими типами математических структур, например с конечными геометриями. Изучались также случайные коды, т.

е. коды, выбираемые случайным образом и не имеющие никакой определенной структуры. Эти коды в книге обсуждаются кратко. Мы отсылаем читателя к работам Возенкрафта 13301, Галлагера 1102, 1031, Шеннона и Уивера 12731, а также к многочисленным работам по случайному кодированию более технического характера. Изучались и блоко. выс, и древовидные случайные коды. Галлагер 11021 предложил эффективную процедуру декодирования для случайных блоковых кодов, Возенкрафт 1330, 3331 и другие авторы [80, 264, 265, 3321 разработали практическую процедуру декодирования, известную как последовательное декодирование, для случайных древовидных кодов.

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

Многие нз таких результатов приведены как упражнения. Некоторые ннх, в основном результаты, связанные с использованием двоичкодов Боуза, Чоудхури и Хоквингема (БЧХ-кодов) для каналов с ошибками и стираниями, включены в основной текст. Поняв канала со стиранием ввел Элайес [67), и к нему прямо или косотносятся все результаты, представленные в этой книге носительно таких каналов.

Общее декодирование для каналов о стиранием было изучено Эпстейном [77). Сверточные коды введены Элайесом [67) и Возенкрафтом [3301 В этой книге рассматриваются декодеры для каналов с д входами и выходами и для двоичного стирающего канала. Изучалось также декодирование для более общих каналов, в которых число выходов превышает число входов [69, 79, 103).

В этих каналах вместе с последовательностью символов декодер получает еще некоторую вполне надежную информацию. Проблема использования этой информации при декодировании блоковых кодов рассматривалась Галлагером [102), Месси [205) и Форни [9Ц. Е1аиболее важные нз известных процедур декодирования для сверточных кодов [205, 312, 330) также могут быть приспособлены для исполь. зования этой надежной информации. Наше современное представление о более общей проблеме кодирования сообщений непрерывными сигналами и тем самым о проблеме полного использования пропускной способности непрерывного канала сравнимо с нашими представлениями пятнадцать лет назад о дискретном канале [173, 271, 280).

Некоторый прогресс достигнут в понимании возможностей двустороннего канала [17, 144, 321, 331[. Галлагер [103) выпустил превосходное общее руководство по теории информации; эта книга содержит много важных результатов, относящихся к теории кодирования, которые если н были доступны до этого времени, то только в журнальных статьях. Все еще представляет большой интерес'классическая основополагающая статья Шеннона [273). Задача 1Л. Постройте таблицу декодирования по методу максималь- ного правдоподобия для двоичного кода, состоящего из четырех кодовых слов 0 0 О О, 0 0 1 1, 1 1 0 0 и 1 1 1 1: а) для двоичного симметричного канала; б) для двоичного стирающего канала. 1.2.

М ° . Метрика определяется как действительная функция, обла- дающая следующими тремя свойствами: А:б(х, )= ность); (х,у) = 0 тогда и только тогда, когда х = у (рефлекси— в- Б:Нх, [): г(х : в(х у) = п(у,х) (симметричность); ( У) » «д(у„з)+ д(х, з) (неравенство треугольника), Покажите, что расстояние Хэмминга является метрикой.

1.3. Предполагается, что совокупность всех получаемых сообщений х, у, ... есть 8 и что на пространстве 5 введена метрика Н(х,у). Пусть передаваемые сообщения также принадлежат 8, Если передано сообщение х, а получено сообщение у, то говорят, что появилась ошибка величины и'(х,у). Код С есть подмножество множества Я, так что если используется код С, то можно считать, что передаются только сообщения хь кь ..., принадлежащие коду С.

Характеристики

Список файлов книги