Теория кодирования - Coding theory

Двумерная визуализация Расстояние Хэмминга, критическая мера в теории кодирования.

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

Есть четыре типа кодирования:^[1]

Сжатие данных (или же исходное кодирование)
Контроль ошибок (или же кодирование каналов)
Криптографическое кодирование
Кодирование строк

Сжатие данных пытается удалить избыточность данных из источника, чтобы передавать их более эффективно. Например, Сжатие данных ZIP уменьшает размер файлов данных, например, для уменьшения интернет-трафика. Сжатие данных и исправление ошибок могут быть учился в сочетании.

Исправление ошибки добавляет дополнительные биты данных, чтобы сделать передачу данных более устойчивой к помехам в канале передачи. Обычный пользователь может не знать о многих приложениях, использующих исправление ошибок. Типичный музыкальный компакт-диск (CD) использует Код Рида-Соломона для устранения царапин и пыли. В этом приложении каналом передачи является сам компакт-диск. Сотовые телефоны также используют методы кодирования для исправления угасание и шум высокочастотной радиопередачи. Модемы данных, телефонные передачи и Сеть дальнего космоса НАСА все используют методы кодирования каналов для передачи битов, например турбо-код и Коды LDPC.

История теории кодирования

В 1948 г. Клод Шеннон опубликовано "Математическая теория коммуникации ", статья в двух частях в июльском и октябрьском выпусках Технический журнал Bell System. В этой работе основное внимание уделяется проблеме того, как лучше всего кодировать Информация отправитель хочет передать. В этой фундаментальной работе он использовал инструменты теории вероятностей, разработанные Норберт Винер, которые в то время находились на начальной стадии своего применения в теории коммуникации. Шеннон разработал информационная энтропия как мера неопределенности в сообщении, по сути изобретая область теория информации.

В двоичный код Голея был разработан в 1949 году. Это код исправления ошибок, способный исправлять до трех ошибок в каждом 24-битном слове и обнаруживать четвертую.

Ричард Хэмминг выиграл Премия Тьюринга в 1968 году за работу в Bell Labs в численных методах, системах автоматического кодирования, кодах для обнаружения и исправления ошибок. Он изобрел концепции, известные как Коды Хэмминга, Окна Хэмминга, Числа Хэмминга, и Расстояние Хэмминга.

В 1972 г. Насир Ахмед предложил дискретное косинусное преобразование (DCT), который он разработал вместе с Т. Натараджаном и К. Р. Рао в 1973 г.^[2] DCT - наиболее широко используемый сжатие с потерями алгоритм, основа для мультимедийных форматов, таких как JPEG, MPEG и MP3.

Исходное кодирование

Цель исходного кодирования - взять исходные данные и уменьшить их.

Определение

Данные можно рассматривать как случайная переменная ${ Displaystyle X: Omega rightarrow { mathcal {X}}}$ , куда ${ displaystyle x in { mathcal {X}}}$ появляется с вероятностью ${ displaystyle mathbb {P} [X = x]}$ .

Данные кодируются строками (словами) над алфавит ${ displaystyle Sigma}$ .

Код - это функция

${ Displaystyle C: { mathcal {X}} rightarrow Sigma ^ {*}}$ (или же ${ Displaystyle Sigma ^ {+}}$ если пустая строка не является частью алфавита).

${ Displaystyle C (х)}$ это кодовое слово, связанное с ${ displaystyle x}$ .

Длина кодового слова записывается как

${ Displaystyle l (С (х))}$ .

Ожидаемая длина кода

${ Displaystyle l (C) = сумма _ {x in { mathcal {X}}} l (C (x)) mathbb {P} [X = x]}$

Объединение кодовых слов ${ Displaystyle C (x_ {1}, ..., x_ {k}) = C (x_ {1}) C (x_ {2}) ... C (x_ {k})}$ .

Кодовое слово пустой строки - это сама пустая строка:

${ Displaystyle С ( эпсилон) = эпсилон}$

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

${ Displaystyle C: { mathcal {X}} rightarrow Sigma ^ {*}}$ является неособый если инъективный.
${ Displaystyle C: { mathcal {X}} ^ {*} rightarrow Sigma ^ {*}}$ является однозначно декодируемый если инъективный.
${ Displaystyle C: { mathcal {X}} rightarrow Sigma ^ {*}}$ является мгновенный если ${ Displaystyle C (x_ {1})}$ не является префиксом ${ Displaystyle C (x_ {2})}$ (наоборот).

Принцип

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

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

Различные методы, используемые схемами кодирования источника, пытаются достичь предела энтропии источника. C(Икс) ≥ ЧАС(Икс), куда ЧАС(Икс) - энтропия источника (битрейт), а C(Икс) - битрейт после сжатия. В частности, никакая схема кодирования источника не может быть лучше, чем энтропия источника.

Пример

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

Кодирование каналов

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

Компакт-диски используют кодирование с перекрестным чередованием Рида – Соломона для распределения данных по диску.^[3]

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

Другие коды больше подходят для разных приложений. Связь в дальнем космосе ограничена тепловой шум приемника, который носит скорее непрерывный характер, чем прерывистый характер. Точно так же узкополосные модемы ограничены шумом, присутствующим в телефонной сети, а также лучше моделируются как непрерывные помехи.^{[нужна цитата ]} Сотовые телефоны подвержены быстрой угасание. Используемые высокие частоты могут вызвать быстрое затухание сигнала даже при перемещении приемника на несколько дюймов. Опять же, есть класс канальных кодов, которые предназначены для борьбы с замираниями.^{[нужна цитата ]}

Линейные коды

Период, термин алгебраическая теория кодирования обозначает подполе теории кодирования, где свойства кодов выражаются в алгебраических терминах и затем исследуются.^{[нужна цитата ]}

Алгебраическая теория кодирования в основном делится на два основных типа кодов:^{[нужна цитата ]}

Линейные блочные коды
Сверточные коды

Он анализирует следующие три свойства кода - в основном:^{[нужна цитата ]}

Длина кодового слова
Общее количество допустимых кодовых слов
Минимум расстояние между двумя допустимыми кодовыми словами, используя в основном Расстояние Хэмминга, иногда и другие расстояния, такие как Расстояние Ли

Линейные блочные коды

Линейные блочные коды обладают свойством линейность, т.е. сумма любых двух кодовых слов также является кодовым словом, и они применяются к исходным битам в блоках, отсюда и название линейные блочные коды. Существуют нелинейные блочные коды, но без этого свойства трудно доказать, что код является хорошим.^[4]

Линейные блочные коды суммируются их алфавитами символов (например, двоичными или троичными) и параметрами (п,м,d_мин)^[5] куда

n - длина кодового слова в символах,
m - количество исходных символов, которые будут использоваться для кодирования сразу,
d_мин - минимальное расстояние Хэмминга для кода.

Есть много типов линейных блочных кодов, таких как

Коды блоков привязаны к упаковка сфер проблема, которой на протяжении многих лет уделялось некоторое внимание. В двух измерениях это легко визуализировать. Возьмите связку монет на столе и сдвиньте их вместе. В результате получился шестиугольник, похожий на пчелиное гнездо. Но блочные коды полагаются на большее количество измерений, которые трудно визуализировать. Мощный (24,12) Код Голея используется в дальнем космосе, используется 24 измерения. При использовании в качестве двоичного кода (как правило, это так) размеры относятся к длине кодового слова, как определено выше.

Теория кодирования использует N-мерная сферическая модель. Например, сколько пенни можно упаковать в круг на столе или в трех измерениях, сколько шариков можно упаковать в глобус. Другие соображения относятся к выбору кода. Например, упаковка шестиугольника в прямоугольную коробку оставит пустые места по углам. По мере увеличения размеров процент пустого пространства становится меньше. Но при определенных размерах упаковка занимает все пространство, и эти коды являются так называемыми «идеальными» кодами. Единственными нетривиальными и полезными совершенными кодами являются коды Хэмминга с расстоянием 3 с параметрами, удовлетворяющими (2^р – 1, 2^р – 1 – р, 3), а также двоичный [23,12,7] и [11,6,5] троичный коды Голея.^[4]^[5]

Другое свойство кода - это количество соседей, которое может иметь одно кодовое слово.^[6]Опять же, рассмотрим в качестве примера гроши. Сначала мы упаковываем пенни в прямоугольную сетку. У каждого пенни будет 4 ближайших соседа (и 4 на дальних углах). В шестиугольнике у каждого пенни будет 6 ближайших соседей. Когда мы увеличиваем размеры, количество ближайших соседей увеличивается очень быстро. В результате увеличивается количество способов, которыми шум заставляет приемник выбирать соседа (а значит, и ошибка). Это фундаментальное ограничение блочных кодов, да и вообще всех кодов. Может быть труднее вызвать ошибку для одного соседа, но количество соседей может быть достаточно большим, поэтому общая вероятность ошибки действительно страдает.^[6]

Свойства линейных блочных кодов используются во многих приложениях. Например, свойство уникальности синдромно-смежного класса линейных блочных кодов используется при формировании решетчатой диаграммы,^[7] один из самых известных коды формирования.

Сверточные коды

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

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

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

В Алгоритм Витерби - оптимальный алгоритм, используемый для декодирования сверточных кодов. Есть упрощения для уменьшения вычислительной нагрузки. Они полагаются на поиск только наиболее вероятных путей. Хотя они и не являются оптимальными, они, как правило, дают хорошие результаты в условиях низкого шума.

Сверточные коды используются в модемах голосового диапазона (V.32, V.17, V.34) и в мобильных телефонах GSM, а также в устройствах спутниковой и военной связи.

Криптографическое кодирование

Криптография или криптографическое кодирование - это практика и изучение методов для безопасное общение в присутствии третьих лиц (называемых противники ).^[8] В более общем плане речь идет о построении и анализе протоколы которые блокируют противников;^[9] различные аспекты в информационная безопасность такие как данные конфиденциальность, целостность данных, аутентификация, и неотречение^[10] занимают центральное место в современной криптографии. Современная криптография существует на пересечении дисциплин математика, Информатика, и электротехника. Приложения криптографии включают Карты банкоматов, компьютерные пароли, и электронная коммерция.

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

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

Кодирование строк

А линейный код (также называемый цифровой модуляцией основной полосы частот или методом цифровой передачи основной полосы частот) код выбран для использования в система связи за основная полоса коробка передач целей. Линейное кодирование часто используется для передачи цифровых данных.

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

Другие приложения теории кодирования

Еще одна проблема теории кодирования - это разработка кодов, которые помогают синхронизация. Код может быть разработан так, чтобы сдвиг фазы могут быть легко обнаружены и исправлены, и что несколько сигналов могут быть отправлены по одному и тому же каналу.^{[нужна цитата ]}

Еще одно приложение кодов, используемое в некоторых системах мобильной связи, - это Кодовым разделением множественного доступа (CDMA). Каждому телефону назначается кодовая последовательность, которая приблизительно не коррелирует с кодами других телефонов.^{[нужна цитата ]} При передаче кодовое слово используется для модуляции битов данных, представляющих речевое сообщение. В приемнике выполняется процесс демодуляции для восстановления данных. Свойства этого класса кодов позволяют множеству пользователей (с разными кодами) одновременно использовать один и тот же радиоканал. Для приемника сигналы других пользователей будут восприниматься демодулятором только как шум низкого уровня.^{[нужна цитата ]}

Другой общий класс кодов - это автоматический повторный запрос (ARQ) коды. В этих кодах отправитель добавляет избыточность к каждому сообщению для проверки ошибок, обычно путем добавления контрольных битов. Если контрольные биты не соответствуют остальной части сообщения, когда оно приходит, получатель попросит отправителя повторно передать сообщение. Все, кроме самого простого Глобальная сеть протоколы используют ARQ. Общие протоколы включают SDLC (IBM), TCP (Интернет), X.25 (Международный) и многие другие. Существует обширная область исследований по этой теме из-за проблемы сопоставления отклоненного пакета с новым пакетом. Это новый или ретрансляция? Обычно используются схемы нумерации, как в TCP."RFC793". RFC. Инженерная группа Интернета (IETF). Сентябрь 1981 г.

Групповое тестирование

Групповое тестирование использует коды по-другому. Рассмотрим большую группу предметов, очень немногие из которых отличаются особым образом (например, дефектные продукты или инфицированные испытуемые). Идея группового тестирования состоит в том, чтобы определить, какие элементы «разные», используя как можно меньше тестов. Корни проблемы лежат в Вторая мировая война когда ВВС армии США нужно было проверить своих солдат на сифилис.^[11]

Аналоговое кодирование

Информация кодируется аналогично в нейронные сети из мозги, в обработка аналогового сигнала, и аналоговая электроника. Аспекты аналогового кодирования включают исправление аналоговых ошибок,^[12]сжатие аналоговых данных^[13] и аналоговое шифрование.^[14]

Нейронное кодирование

Нейронное кодирование это нейробиология -связанное поле, связанное с тем, как сенсорная и другая информация представлена в мозг к сети из нейроны. Основная цель изучения нейронного кодирования - охарактеризовать взаимосвязь между стимул и индивидуальные или совокупные нейронные ответы и взаимосвязь между электрической активностью нейронов в ансамбле.^[15] Считается, что нейроны могут кодировать как цифровой и аналог Информация,^[16] и что нейроны следуют принципам теории информации и сжимают информацию,^[17] и обнаружить и исправить^[18]ошибки в сигналах, которые посылаются через мозг и нервную систему в целом.

Смотрите также

Прирост кодирования
Код покрытия
Код исправления ошибок
Сложенный код Рида – Соломона
Групповое тестирование
Расстояние Хэмминга, Вес Хэмминга
Расстояние Ли
Список тем по алгебраической теории кодирования
Пространственное кодирование и MIMO в исследовании нескольких антенн
- Кодирование пространственного разнообразия - это пространственное кодирование, которое передает копии информационного сигнала по разным пространственным путям, чтобы повысить надежность передачи данных.
- Кодирование с подавлением пространственных помех
- Кодирование пространственного мультиплексирования
Хронология теории информации, сжатия данных и кодов исправления ошибок

Примечания

^ Джеймс Ирвин; Дэвид Харл (2002). «2.4.4 Типы кодирования». Передача данных и сети. п. 18. ISBN 9780471808725. Есть четыре типа кодирования
^ Насир Ахмед. "Как я пришел к дискретному косинусному преобразованию". Цифровая обработка сигналов, Vol. 1, вып. 1, 1991, стр. 4-5.
^ Тодд Кэмпбелл."Answer Geek: компакт-диски с правилами исправления ошибок".
^ ^а ^б Террас, Одри (1999). Анализ Фурье на конечных группах и приложениях. Издательство Кембриджского университета. п.195. ISBN 978-0-521-45718-7.
^ ^а ^б Блахут, Ричард Э. (2003). Алгебраические коды для передачи данных. Издательство Кембриджского университета. ISBN 978-0-521-55374-2.
^ ^а ^б Кристиан Шлегель; Лэнс Перес (2004). Решетки и турбо-кодирование. Wiley-IEEE. п. 73. ISBN 978-0-471-22755-7.
^ Форни, Г.Д., мл. (Март 1992 г.). «Формовка решеток». IEEE Transactions по теории информации. 38 (2 Pt 2): 281–300. Дои:10.1109/18.119687.
^ Ривест, Рональд Л. (1990). «Криптология». В J. Van Leeuwen (ред.). Справочник по теоретической информатике. 1. Эльзевир.
^ Белларе, Михир; Рогавей, Филипп (21 сентября 2005 г.). "Вступление". Введение в современную криптографию. п. 10.
^ Menezes, A.J .; van Oorschot, P.C .; Ванстон, С. А. (1997). Справочник по прикладной криптографии. ISBN 978-0-8493-8523-0.
^ Дорфман, Роберт (1943). «Выявление дефектных представителей больших популяций». Анналы математической статистики. 14 (4): 436–440. Дои:10.1214 / aoms / 1177731363.
^ Чен, Брайан; Уорнелл, Грегори В. (июль 1998 г.). «Аналоговые коды с исправлением ошибок на основе хаотических динамических систем» (PDF). Транзакции IEEE по коммуникациям. 46 (7): 881–890. CiteSeerX 10.1.1.30.4093. Дои:10.1109/26.701312. Архивировано из оригинал (PDF) на 2001-09-27. Получено 2013-06-30.
^ Новак, Франк; Хвала, Боян; Клавжар, Санди (1999). «Об анализе аналоговой сигнатуры». Материалы конференции по проектированию, автоматизации и тестированию в Европе. CiteSeerX 10.1.1.142.5853. ISBN 1-58113-121-6.
^ Шуджун Ли; Чэнцин Ли; Квок-Тунг Ло; Гуаньжун Чен (апрель 2008 г.). «Криптоанализ схемы шифрования на основе слепого разделения источников» (PDF). Транзакции IEEE в схемах и системах I. 55 (4): 1055–63. arXiv:cs / 0608024. Дои:10.1109 / TCSI.2008.916540.
^ Brown EN, Kass RE, Mitra PP (май 2004 г.). «Анализ данных множественных нейронных спайков: современное состояние и будущие задачи» (PDF). Природа Неврология. 7 (5): 456–461. Дои:10.1038 / nn1228. PMID 15114358.
^ Торп, С.Дж. (1990). «Время прихода пиков: высокоэффективная схема кодирования для нейронных сетей» (PDF). В Eckmiller, R .; Hartmann, G .; Хауске, Г. (ред.). Параллельная обработка в нейронных системах и компьютерах (PDF). Северная Голландия. С. 91–94. ISBN 978-0-444-88390-2. Получено 30 июн 2013.
^ Гедеон, Т .; Parker, A.E .; Димитров А.Г. (весна 2002 г.). «Искажение информации и нейронное кодирование». Canadian Applied Mathematics Quarterly. 10 (1): 10. CiteSeerX 10.1.1.5.6365.
^ Стибер, М. (июль 2005 г.). «Пиковая точность синхронизации и исправление нейронных ошибок: локальное поведение». Нейронные вычисления. 17 (7): 1577–1601. arXiv:q-bio / 0501021. Дои:10.1162/0899766053723069. PMID 15901408.