Что изучает теория кодирования кратко

Обновлено: 05.07.2024

Теория коди́рования — наука о свойствах кодов и их пригодности для достижения поставленной цели.

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

При использовании людьми одна и та же информация может иметь различную оценку с точки зрения значимости (важности, ценности).

Техническое устройство не может оценить важности информации – его задача без потерь передать или сохранить информацию.

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

Следовательно, появляется возможность объективного измерения информации, при этом результат измерения – абсолютен.

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

С точки зрения формальной информации страница из учебника информатики или из романа "Война и мир" и страница, записанная бессмысленными значками, содержат одинаковое количество информации.

Количественная сторона информации объективна, смысловая – нет. Однако, жертвуя смысловой (семантической) стороной информации, мы получаем объективные методы измерения ее количества, а также обретаем возможность описывать информационные процессы математическими уравнениями.

Это является условием применимости законов теории информации к анализу и описанию информационных процессов.

На этом шаге мы рассмотрим понятие и основные задачи теории кодирования.

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

· разработка принципов наиболее экономичного кодирования информации;

· согласование параметров передаваемой информации с особенностями канала связи;

· разработка приемов, обеспечивающих надежность передачи информации по каналам связи, т.е. отсутствие потерь информации.

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

С обсуждения этих вопросов и начнем освоение теории кодирования.

Основные определения теории кодирования

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

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

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

Условимся называть алфавит, с помощью которого представляется информация до преобразования, первичным; алфавит конечного представления – вторичным.

Введем ряд с определений:

Код – (1) правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита; - (2) знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита.

Кодирование – перевод информации, представленной посредством первичного алфавита, в последовательность кодов.

Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.

Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.

Примером обратимого кодирования является представление знаков в телеграфном коде и их восстановление после передачи.

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

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

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

Эти состояния или сигналы будем называть элементарными сигналами – именно их совокупность и составляет вторичный алфавит.

Объективность информации.

На этом шаге мы рассмотрим понятие и основные задачи теории кодирования.

· разработка принципов наиболее экономичного кодирования информации;

· согласование параметров передаваемой информации с особенностями канала связи;

С обсуждения этих вопросов и начнем освоение теории кодирования.

Основные определения теории кодирования

Введем ряд с определений:

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

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

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

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

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

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

Содержание

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

C : Икс → Σ ∗ < Displaystyle C: < mathcal > rightarrow Sigma ^ > является неособый если инъективный.
C : Икс ∗ → Σ ∗ < Displaystyle C: < mathcal > ^ rightarrow Sigma ^ > является однозначно декодируемый если инъективный.
C : Икс → Σ ∗ < Displaystyle C: < mathcal > rightarrow Sigma ^ > является мгновенный если C ( Икс 1 ) < Displaystyle C (x_ )> не является префиксом C ( Икс 2 ) < Displaystyle C (x_ )> (наоборот).

Принцип

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта статья или раздел может содержать вводящие в заблуждение части. Пожалуйста помоги проясните эту статью согласно любым предложениям, представленным на страница обсуждения. ( Август 2012 г. )

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

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

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

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

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

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

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

Хэмминг опубликовал свою статью в 1950 году, хотя во внутренних отчетах его теория кодирования датируется 1947 годом. Поэтому некоторые считают, что отцом теории кодирования следует считать Хэмминга, а не Шеннона. Впрочем, в истории техники бесполезно искать первого.

Ричард Хэмминг (1915 — 1998) начал свое образование в Чикагском университете, где в 1937 году получил степень бакалавра. В 1939 году он получил степень магистра в Университете Небраски, а степень доктора по математике — в Университете Иллинойса. В 1945 году Хэмминг начал работать в рамках Манхэттенского проекта — масштабной государственной научно-исследовательской работы по созданию атомной бомбы. В 1946 году Хэмминг поступил на работу в Bell Telephone Laboratories, где работал в том числе с Клодом Шенноном. В 1976 году Хэмминг получил кафедру в военно-морской аспирантуре в Монтерей в Калифорнии.

Труд, сделавший его знаменитым, фундаментальное исследование кодов обнаружения и исправления ошибок, Хэмминг опубликовал в 1950 году. В 1956 году он принимал участие в работе над одним из ранних мэйнфреймов IBM 650. Его работы заложили основу языка программирования, который позднее эволюционировал в языки программирования высокого уровня. В знак признания заслуг Хэмминга в области информатики институт IEEE учредил медаль за выдающиеся заслуги в развитии информатики и теории систем, которую назвал его именем.

Читайте также: