Теория кодирования

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

Данные кодируются строками (словами) в алфавите . $\Сигма$

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

C:{\mathcal {X}}\to \Sigma ^{*}

(или если пустая строка не является частью алфавита).

\Sigma ^{+}

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

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

l(C(x)).

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

l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].

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

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

C(\epsilon )=\epsilon

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

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

Принцип

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

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

Различные методы, используемые схемами кодирования источника, пытаются достичь предела энтропии источника. C ( x ) ≥ H ( x ), где H ( x ) — энтропия источника (битрейт), а C ( x ) — битрейт после сжатия. В частности, никакая схема кодирования источника не может быть лучше, чем энтропия источника.

Пример

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

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

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

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

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

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

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

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

^{Теория алгебраического кодирования в} основном делится на два основных типа ^кодов^:

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

Он анализирует следующие три свойства кода – ^{в основном :}

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

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

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

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

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

Существует много типов линейных блочных кодов, например

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

Теория кодирования использует N -мерную сферную модель. Например, сколько монет можно упаковать в круг на столе или в трех измерениях, сколько шариков можно упаковать в глобус. Другие соображения влияют на выбор кода. Например, упаковка шестиугольника в ограничение прямоугольной коробки оставит пустое пространство в углах. По мере увеличения размеров процент пустого пространства уменьшается. Но при определенных размерах упаковка занимает все пространство, и эти коды являются так называемыми «идеальными» кодами. Единственными нетривиальными и полезными совершенными кодами являются коды Хэмминга на расстоянии 3 с параметрами, удовлетворяющими (2 ^r – 1, 2 ^r – 1 – r , 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». РФКС . Целевая группа инженеров Интернета (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. ИСБН 978-0-521-45718-7.
^ аб Блаут, Ричард Э. (2003). Алгебраические коды для передачи данных. Издательство Кембриджского университета. ISBN 978-0-521-55374-2.
^ аб Кристиан Шлегель; Лэнс Перес (2004). Треллис и турбокодирование. Вайли-IEEE. п. 73. ИСБН 978-0-471-22755-7.
^ Форни, Дж. Д. младший (март 1992 г.). «Формирование шпалеры». Транзакции IEEE по теории информации . 38 (2, часть 2): 281–300. дои : 10.1109/18.119687. S2CID 37984132.
^ Ривест, Рональд Л. (1990). «Криптология». В Дж. Ван Леувене (ред.). Справочник по теоретической информатике . Том. 1. Эльзевир.
^ Белларе, Михир; Рогауэй, Филипп (21 сентября 2005 г.). "Введение". Введение в современную криптографию . п. 10.
^ Менезес, AJ; ван Ооршот, ПК; Ванстон, ЮАР (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) 27 сентября 2001 г. Проверено 30 июня 2013 г.
^ Новак, Франк; Хвала, Боян; Клавжар, Санди (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. S2CID 2224947.
^ Браун Э.Н., Касс Р.Э., Митра П.П. (май 2004 г.). «Анализ данных множественных нейронных импульсов: современное состояние и проблемы будущего» (PDF) . Природная неврология . 7 (5): 456–461. дои : 10.1038/nn1228. PMID 15114358. S2CID 562815.
^ Торп, SJ (1990). «Время прибытия пиков: высокоэффективная схема кодирования для нейронных сетей» (PDF) . В Экмиллере, Р.; Хартманн, Г.; Хауске, Г. (ред.). Параллельная обработка в нейронных системах и компьютерах (PDF) . Северная Голландия. стр. 91–94. ISBN 978-0-444-88390-2. Проверено 30 июня 2013 г.
^ Гедеон, Т.; Паркер, А.Э.; Димитров, А.Г. (весна 2002 г.). «Искажение информации и нейронное кодирование». Ежеквартальный журнал канадской прикладной математики . 10 (1): 10. CiteSeerX 10.1.1.5.6365 . Архивировано из оригинала 17 ноября 2016 г. Проверено 30 июня 2013 г.
^ Стибер, М. (июль 2005 г.). «Точность синхронизации всплесков и коррекция нейронных ошибок: локальное поведение». Нейронные вычисления . 17 (7): 1577–1601. arXiv : q-bio/0501021 . дои : 10.1162/0899766053723069. PMID 15901408. S2CID 2064645.