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

редактировать

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

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

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

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

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

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

Содержание

1 История теории кодирования
2 Исходное кодирование
- 2.1 Определение
- 2.2 Свойства
- 2.3 Принцип
- 2.4 Пример
3-канальное кодирование
- 3.1 Линейные коды
  - 3.1.1 Линейные блочные коды
  - 3.1.2 Сверточные коды
4 Криптографическое кодирование
5 Линейное кодирование
6 Другие приложения теории кодирования
- 6.1 Групповое тестирование
- 6.2 Аналоговое кодирование
7 Нейронное кодирование
8 См. Также
9 Примечания
10 Ссылки

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

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

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

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

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

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

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

Определение

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

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

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

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

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

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

$l (C (x)) {\ displaystyle l (C (x))}$ $l (C (x))$ .

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

$l (C) = ∑ x ∈ X l (C (x)) P [X = x] {\ displaystyle l (C) = \ sum _ {x \ in {\ mathcal {X}}} l (C (x)) \ mathbb {P} [X = x]}$ $l (C) = \ sum _ {x \ in {\ mathcal {X}}} l (C (x)) \ mathbb {P} [X = x]$

Конкатенация кода слова $C (x 1,...., xk) = C (x 1) C (x 2)... С (xk) {\ displaystyle C (x_ {1},..., x_ {k}) = C (x_ {1}) C (x_ {2})... C (x_ {k})}$ $C ( x_ {1},..., x_ {k}) = C (x_ {1}) C (x_ {2})... C (x_ {k})$ .

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

$C (ϵ) = ϵ {\ displaystyle C (\ epsilon) = \ epsilon}$ $C (\ epsilon) = \ epsilon$

Свойства

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

Принцип

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

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

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

Пример

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

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

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

CD используют перекрестное чередование кодирования Рида – Соломона для распределения данных по диску.

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

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

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

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

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

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

Это анализирует следующие три свойства кода - в основном:

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

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

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

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

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

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

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

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

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

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

сверточных кодов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

Телекоммуникационный портал

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

Примечания

Ссылки

Элвин Р. Берлекамп (2014), Algebraic Coding Theory, World Scientific Publishing (исправленное издание), ISBN 978-9-81463-589-9.
Маккей, Дэвид Дж. К.. Теория информации, логический вывод и алгоритмы обучения Кембридж: Cambridge University Press, 2003. ISBN 0-521-64298-1
Вера Плесс (1982), Введение в теорию кодов с исправлением ошибок, John Wiley Sons, Inc., ISBN 0-471-08684-3.
Рэнди Йейтс, Руководство по теории кодирования.