Теория кодирования. Основы теории информации и кодирования. Классификация методов кодирования

04.04.2006 Леонид Черняк Рубрика:Технологии

«Открытые системы» Создание компьютеров было бы невозможно, если одновременно с?их появлением не была бы создана теория кодирования сигналов Теория кодирования?- одна из тех областей математики, которые заметно повлияли на развитие компьютинга.

«Открытые системы»

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

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

С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надежности передачи телеграмм. Проблема еще более обострилась в связи с прокладкой трансатлантических кабелей. С 1845 года вошли в употребление специальные кодовые книги; с их помощью телеграфисты вручную выполняли «компрессию» сообщений, заменяя распространенные последовательности слов более короткими кодами. Тогда же для проверки правильности передачи стали использовать контроль четности, метод, который применялся для проверки правильности ввода перфокарт еще и в компьютерах первого и второго поколений. Для этого во вводимую колоду последней вкладывали специально подготовленную карту с контрольной суммой. Если устройство ввода было не слишком надежным (или колода - слишком большой), то могла возникнуть ошибка. Чтобы исправить ее, процедуру ввода повторяли до тех пор, пока подсчитанная контрольная сумма не совпадала с суммой, сохраненной на карте. Мало того, что эта схема неудобна, она к тому же пропускает двойные ошибки. С развитием каналов связи потребовался более эффективный механизм контроля.

Первым теоретическое решение проблемы передачи данных по зашумленным каналам предложил Клод Шеннон, основоположник статистической теории информации. Шеннон был звездой своего времени, он входил в академическую элиту США. Будучи аспирантом Ванневара Буша, в 1940 году он получил премию имени Нобеля (не путать с Нобелевской премией!), присуждаемую ученым, не достигшим 30 лет. Работая в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. Это умозаключение содержится в одной из доказанных Шенноном теорем, ее смысл сводится к тому, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал теоретическую возможность достоверной передачи при наличии шума в канале. Формулу C = W log ((P+N)/N), высеченную на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган, сравнивают по значению с формулой Альберта Эйнштейна E = mc 2 .

Труды Шеннона дали пищу для множества дальнейших исследований в области теории информации, но практического инженерного приложения они не имели. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по Bell Labs, получившего известность за открытие класса кодов, которые так и стали называть «кодами Хэмминга». Существует легенда, что к изобретению своих кодов Хэмминга подтолкнуло неудобство в работе с перфокартами на релейной счетной машине Bell Model V в середине 40-х годов. Ему давали время для работы на машине в выходные дни, когда не было операторов, и ему самому приходилось возиться с вводом. Как бы то ни было, но Хэмминг предложил коды, способные корректировать ошибки в каналах связи, в том числе и в магистралях передачи данных в компьютерах, прежде всего между процессором и памятью. Коды Хэмминга стали свидетельством того, как можно практически реализовать возможности, на которые указывают теоремы Шеннона.

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

Достоверно только то, что именно Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC). Современные модификации этих кодов используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, которые могли бы вызвать царапины и пылинки. Существует множество версий кодов, построенных «по мотивам» Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение подобные коды приобрели в связи с развитием дальней космической связи с межпланетными станциями, например, существуют коды Рида-Мюллера, где на семь информационных битов приходится 32 контрольных, или на шесть - 26.

Среди новейших кодов ECC следует назвать коды LDPC (Low-Density Parity-check Code). Вообще-то они известны лет тридцать, но особый интерес к ним обнаружился именно в последние годы, когда стало развиваться телевидение высокой четкости. Коды LDPC не обладают 100-процентной достоверностью, но вероятность ошибки может быть доведена до желаемой, и при этом с максимальной полнотой используется пропускная способность канала. К ним близки «турбокоды» (Turbo Code), они эффективны при работе с объектами, находящимися в условиях далекого космоса и ограниченной пропускной способности канала.

В историю теории кодирования прочно вписано имя Владимира Александровича Котельникова. В 1933 году в «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи» он опубликовал работу «О пропускной способности?эфира? и?проволоки?». Имя Котельникова на правах равного входит в название одной из важнейших теорем теории кодирования. Этой теоремой определяются условия, при которых переданный сигнал может быть восстановлен без потери информации.

Эту теорему называют по-разному, в том числе «теоремой WKS» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). В некоторых источниках используют и Nyquist-Shannon sampling theorem, и Whittaker-Shannon sampling theorem, а в отечественных вузовских учебниках чаще всего встречается просто «теорема Котельникова». На самом же деле теорема имеет более долгую историю. Ее первую часть в 1897 году доказал французский математик Эмиль Борель. Свой вклад в 1915 году внес Эдмунд Уиттекер. В 1920 году японец Кинносуки Огура опубликовал поправки к исследованиям Уиттекера, а в 1928 году американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.

Клод Шеннон (1916 - 2001) со школьных лет проявлял равный интерес к математике и электротехнике. В 1932 году он поступил в Университет штата Мичиган, в 1936-м - в Массачусетский технологический институт, который закончил в 1940 году, получив две степени - магистра по электротехнике и доктора в области математики. В 1941 году Шеннон поступил на работу в Bell Laboratories. Здесь он начал развивать идеи, которые впоследствии вылились в теорию информации. В 1948-м Шеннон опубликовал статью «Математическая теория связи», где были сформулированы базовые идеи ученого, в частности, определение количества информации через энтропию, а также предложил единицу информации, определяющую выбор из двух равновероятных вариантов, то есть то, что впоследствии назвали битом. В 1957-1961 годах Шеннон опубликовал работы, где доказывалась теорема о пропускной способности зашумленных каналов связи, которая теперь носит его имя. В 1957 году Шеннон стал профессором Массачусетского технологического института, откуда ушел на пенсию спустя 21 год. На «заслуженном отдыхе» Шеннон полностью отдался своему давнему увлечению жонглированием. Он построил несколько жонглирующих машин и даже создал общую теорию жонглирования.

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

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

Владимир Котельников (1908 - 2005) в 1926 году поступил на Электротехнический факультет Московского высшего технического училища имени Н. Э. Баумана (МВТУ), но стал выпускником Московского энергетического института (МЭИ), который выделился из МВТУ как самостоятельный институт. Во время обучения в аспирантуре (1931-1933) Котельников математически точно сформулировал и доказал «теорему отсчетов», которая впоследствии была названа его именем. После окончания аспирантуры в 1933 году Котельников, оставаясь преподавать в МЭИ, поступил на работу в Центральный научно-исследовательский институт связи (ЦНИИС). В 1941 году В. А. Котельников сформулировал четкое положение о том, каким требованиям должна удовлетворять математически недешифруемая система и дано доказательство невозможности ее дешифровки. В 1944 году Котельников занял должность профессора, декана радиотехнического факультета МЭИ, где проработал до 1980 года. В 1953 году в возрасте 45 лет Котельников был избран сразу действительным членом Академии наук СССР. С 1968 по 1990 год В. А. Котельников был также профессором, заведующим кафедрой Московского физико-технического института.

Рождение теории кодирования

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

Объектом кодирования служит как дискретная, так и непрерывная информация, которая поступает к потребителю через источник информации. Понятие кодирование означает преобразование информации в форму, удобную для передачи по определенному каналу связи.

Обратная операция - декодирование – заключается в восстановлении принятого сообщения из закодированного вида в общепринятый, доступный для потребителя.

В теории кодирования существует ряд направлений:

статическое или эффективное кодирование;
помехоустойчивое кодирование;
корректирующие коды;
циклические коды;
арифметические коды.

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

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

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

Если все кодовые слова имеют одинаковую длину, то код называется равномерным, или блочным.

Под абстрактным алфавитом будем понимать упорядоченное дискретное множество символов.

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

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

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

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

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

Однако, ограниченный набор из 256 кодов символов сегодня уже не удовлетворяет возросшие потребности международного общения. Все большее распространение получает универсальная система 16-разрядного кодирования символов UNICODE .

Мощность алфавита в системе кодирования UNICODE составляет 216=65 536 разных кодов, из которых 63 484 кода соответствуют символам большинства алфавитов, а оставшиеся 2048 кодов разделены пополам и образуют таблицу размером 1024 столбцов х 1024 строк. В этой таблице более миллиона ячеек, в которых можно разместить еще более миллиона различных символов. Это символы «мертвых» языков, а также символы, не имеющие лексического содержания, указатели, знаки и т.п. Для записи этих дополнительных символов необходима пара 16-разрядных слов (16 разрядов для номера строки и 16 разрядов для номера столбца).

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

Кодирование изображений

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

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

При кодировании цветных изображений применяют принцип декомпозиции цвета на составляющие, для этого используют модель RGB . Цветное изображение на экране получается путем смешивания трех базовых цветов: красного (Red, R), синего (Blue, B) и зеленого (Green, G).

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

Цветные дисплеи, использующие такой принцип называются RGB -мониторами.

Код цвета пикселя содержит информацию о доле каждого базового цвета.

схема цветообразования

Если все три составляющих имеют одинаковую интенсивность (яркость), то из их сочетаний можно получить 8 различных цветов (23):








			Коричневый

Формирование цветов при глубине цвета 24 бита:

Чем больше глубина цвета, тем шире диапазон доступных цветов и тем точнее их представление в оцифрованном изображении. Пиксель с битовой глубиной, равной единице, имеет лишь 2 (в первой степени) возможных состояния — два цвета: черный или белый. Пиксель с битовой глубиной в 8 единиц имеет 28 или 256 возможных цветовых значений. Пиксель же с битовой глубиной в 24 единицы имеет 224 степени) или 16,7 миллионов возможных значений. Считается, что 24-битные изображения, содержащие 16,7 миллионов цветов, достаточно точно передают краски окружающего нас мира. Как правило, битовое разрешение задается в диапазоне от 1 до 48 бит/пиксель.

При печати на бумаге используется несколько иная цветовая модел: если монитор испускал свет, оттенок получался в результате сложения цветов, то краски - поглощают свет, цвета вычитаются. Поэтому в качестве основных используют голубую (Cyan, C), пурпурную (Magenta, M) и желтую (Yellow, Y) краски. Кроме того, из-за не идеальности красителей, к ним обычно добавляют четвертую -- черную (black, K). Для хранения информации о каждой краске и в этом случае чаще всего используется 1 байт. Такая система кодирования носит название CMYK .

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

Кодирование звука и видео

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

Этот метод кодирования содержит погрешность, так что воспроизводимый сигнал несколько отличается от оригинала.

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

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

04.04.2006 Леонид Черняк Рубрика:Технологии

«Открытые системы»

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

Рождение теории кодирования

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

Тема 5.2. Алфавитное кодирование В общем случае задачу кодирования можно представить следующим образом. Пусть заданы два алфавита А и В, состоящие из конечного числа символов: и. Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом,где обозначается п =l()=| |. , число п показывает количество букв в слове и называется длиной слова, Пустое слово обозначается: Для слова буква a1, называется началом, или префиксом, слова буква an - окончанием, или постфиксом, слова. , а Слова можно соединять. Для этого префикс второго слова должен следовать сразу за постфиксом первого, при этом в новом слове они, естественно, утрачивают свой статус, если только одно из слов не было пустым. Соединение слов и обозначается, соединение п одинаковых слов обозначается, причем. Множество всех непустых слов алфавита А обозначим А*: Множество А называют алфавитом сообщений, а множество В - кодирующим алфавитом. Множество слов, составленных в алфавите В, обозначим В*.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово назовем кодом слова. Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код - правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без какихлибо потерь информации. Процесс преобразования F: А* В*→ слов исходного алфавита А в алфавит В называется кодированием информации. Процесс обратного преобразования слова называется декодированием. Таким образом, декодирование - функция, обратная F, т.е. F1. в слово Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция). Если |B|= m, то F называется mичным кодированием, наиболее распространенный случай В = {0, 1} двоичное кодирование. Именно этот случай и рассматривается в дальнейшем. Если все кодовые слова имеют одинаковую длину, то код на зывается равномерным, или блочным. Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка. Тогда, где, . Такое побуквенное кодирование обозначается называется множеством элементарных кодов. Алфавитное кодирование можно использовать для любого множества сообщений. Таким образом, алфавитное кодирование является самым простым, и его всегда можно ввести на непустых алфавитах. . Множество кодов букв

ПРИМЕР Пусть заданы алфавиты А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} В = {0, 1}. Тогда таблица кодирования может быть подстановкой: . Это двоичнодесятичное кодирование, оно является взаимнооднозначным и потому допускает декодирование. Однако схема не является взаимнооднозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77, а также 111111, 137, 3311 или 7111 плюс любая перестановка. Схема алфавитного кодирования называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы. Схема алфавитного кодирования называется разделимой, если любое слово, составлен ное из элементарных кодов, разлагается на элементарные коды единственным образом. Алфавитное кодирование с разделимой схемой допускает декодирование. Можно доказать, что префиксная схема является разделимой. Для того чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли соотношению, известному какнеравенство Макмиллана. Неравенство Макмиллана Если схема алфавитного кодирования

разделима, то справедливо неравенство ПРИМЕР Схема алфавитного кодирования А={ а, b} и В={0, 1}, является разделимой, т. к. , и, значит, выполняется неравенство Макмиллана Данная схема префиксной не является, т.к. элементарный код буквы а является префиксом элементарного кода буквы b. Тема 5.3. Кодирование с минимальной избыточностью На практике важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, если же про множество всех слов алфавита А ничего не известно, то точно сформулировать задачу оптимизации трудно. Однако на практике часто доступна дополнительная информация. Например, для сообщений, представленных на естественном языке, такой дополнительной информацией может быть распределение вероятности появления букв в сообщении. Тогда задача построения оптимального кода приобретает точную математическую формулировку и строгое решение.

Пусть задана некоторая разделимая схема алфавитного кодирования. Тогда любая схема, где упорядоченный набор есть перестановка упорядоченного, также будет разделимой. В таком случае, если длины элементарных набора кодов равны, то их перестановка в схеме не влияет на длину закодированного сообщения. В том случае, если длины элементарных кодов различны, то длина кода сообщения напрямую зависит и от того, какие элементарные коды каким буквам поставлены в соответствие, и от того, каков состав букв в сообщении. Если заданы конкретное сообщение и конкретная схема кодирования, то можно подобрать такую перестановку кодов, при которой длина кода сообщения будет минимальной. Алгоритм назначения элементарных кодов, при котором длина кода фиксированного сообщения S будет минимальна при фиксированной схеме: ۞ отсортировать буквы в порядке убывания количества вхождений; ۞ отсортировать элементарные коды в порядке возрастания длины; ۞ поставить коды в соответствие буквам в установленном порядке. Пусть задан алфавит и вероятности появления букв в сообщении:

Где рi - вероятность появления буквы ai, причем буквы с нулевой вероятностью появления в сообщении исключены и буквы упорядочены по убыванию вероятности их появления Для разделимой схемы алфавитного кодирования при распределении вероятностей Р существует так называемая средняя цена, или длина кодирования, - это математическое ожидание длины закодированного сообщения, которая обозначается и определяется как ПРИМЕР. Для разделимой схемы алфавитного кодирования А={а,b}, В={0,1}, при распределении вероятностей цена кодирования составляет а при распределении вероятностей цена кодирования составляет

Тема 5.4. Кодирование методом Хаффмана Этот алгоритм был изобретен в 1952 году Дэвидом Хаффманом. Тема 5.5. Арифметическое кодирование Как и в алгоритме Хаффмана, все начинается с таблицы элементов и соответствующих вероятностей. Допустим, входной алфавит состоит всего из трех элементов: a1, a2 и a3, и при этом P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Предположим также, что нам надо закодировать последовательность a1, a1, a2, a3 . Разобьем полуинтервал , где р некотороефиксированное число, 0<р<(r1)/2r, а "мощностная" граница где Tr(p)=p logr(p/(r 1))(1р)logr(l p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для крого существует декодер,состоящий из регист

ра сдвига и одного мажоритарного элемента и исправляющий одну ошибку, имеетпорядок (ср. с (2)). В качестве математич. модели кодера и декодера обычно рассматривают с хемы изфункциональных элементов и под сложностью понимают число элементов в схеме. Для известных классовкодов с исправлением ошибок проведено исследование возможных а лгоритмов К. и д. и получены верхниеграницы сложности кодера и декодера. Найдены такж е некрые соотношения между скоростью передачикодирования, помехоустойчивостью код ирования и сложностью декодера (см. ). Еще одно направление исследований в теории кодирования связано с тем, что многие резул ьтаты (напр.,теорема Шеннона и граница (3)) не являются "конструктивными", а представл яют собой теоремысуществования бесконечных последовательностей {К п} кодов В связи с этим предпринимаютсяусилия, чтобы доказать эти результаты в классе таких последовательностей {К п} кодов, для крых существуетмашина Тьюринга, распознаю щая принадлежность произвольного слова длины lмножеству завремя, имеющее м едленный порядок роста относительно l(напр., llog l). Некрые новые конструкции и методы получения границ, разработанные в теории кодирова ния, привели ксущественному продвижению в вопросах, на первый взгляд весьма далеких о т традиционных задач теориикодирования. Здесь следует указать на использование максим ального кода с исправлением одной ошибки васимптотически оптимальном методе реализа ции функций алгебры логики контактными схемами;напринципиальное улучшение верхне й границы для плотности упаковки reмерного евклидова пространстваравными шарами; на использование неравенства (1) при оценке сложности реализации формулами одногокласса функций алгебры логики. Идеи и результаты теории кодирования находят свое дальнейшее развитие взадачах синтеза самокорректирующихся схем и надежных схем из ненадежных эл ементов. Лит.: Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; Берлекэмп Э.,Алгебраическая теория кодирования, пер. с англ., М., 1971; Питерсон У., Уэлдон Э., Коды, исправляющиеошибки, пер. с англ., 2 изд., М., 1976; Дискретная математика и математические вопросы кибернетики, т.1,М., 1974, раздел 5; Бассалыго Л. А., Зяблов В. В., Пинскер М. С, "Пробл. передачи информации", 1977, т.13, № 3, с. 517; [В] Сидельников В. М., "Матем. сб.", 1974, т. 95, в. 1, с. 148 58. В. И. Левенштейн.

Математическая энциклопедия. - М.: Советская энциклопедия. И. М. Виноградов. 1977-1985.  КОДИРОВАНИЕ АЛФАВИТНОЕ  КОЕВКЛИДОВО ПРОСТРАНСТВО См. также в других словарях:  ДЕКОДИРОВАНИЕ - см. Кодирование и декодирование … Математическая энциклопедия  Кодирование звуковой информации - Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. В основе кодирования звука с использованием ПК лежит процесс преобразования колебаний воздуха в колебания электрическог … Википедия  КОДИРОВАНИЕ - (от франц. code – свод законов, правил) – отображение (преобразование) нек рых объектов (событий, состояний) в систему конструктивных объектов (называемых кодовыми образами), совершаемое по определ. правилам, совокупность к рых наз. шифром К.,… … Философская энциклопедия  КОДИРОВАНИЕ ИНФОРМАЦИИ - установление соответствия между элементами сообщения и сигналами, при помощи к рых эти элементы могут быть зафиксированы. Пусть В, множество элементов сообщения, А алфавит с символами, Пусть конечная последовательность символов наз. словом в… … Физическая энциклопедия  КОДИРОВАНИЕ ОПТИМАЛЬНОЕ - (в инженерной психологии) (англ. optimal coding) создание кодов, обеспечивающих максимальную скорость и надежность приема и переработки информации об объекте управления человеком оператором (см. Прием информации, Декодирование). Проблема К. о.… … Большая психологическая энциклопедия  ДЕКОДИРОВАНИЕ (в инженерной психологии) - (англ. decoding) заключительная операция процесса приема информации человеком оператором, состоящая в перешифровке параметров, характеризующих состояние объекта управления, и в переводе их в образ управляемого объекта (см. Кодирование… … Большая психологическая энциклопедия

 Декодирование - восстановление сообщения, закодированного переданными и принятыми сигналами (см. Кодирование) … Экономико математический словарь  КОДИРОВАНИЕ - КОДИРОВАНИЕ. Один из этапов порождения речи, в то время как «декодирование» – прием и интерпретация, процесс понимания речевого сообщения. См. психолингвистика … Новый словарь методических терминов и понятий (теория и практика обучения языкам)  КОДИРОВАНИЕ - (англ. coding). 1. Преобразование сигнала из одной энергетической формы в др. 2. Преобразование одной системы сигналов или знаков в др., что часто называется также «перекодированием», «сменой кода» (для речи «перевод»). 3. К. (мнемическое)… … Большая психологическая энциклопедия  Декодирование - Эта статья о коде в теории информации, другие значения этого слова см. в код (значения). Код правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков) (или сигналов). Кодом также называется… … Оптимальное кодирование Одно и то же сообщение можно закодировать различными способами. Оптимально закодированным будем считать такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (0 или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет иметь минимально возможную длину. Пример 1. Пусть имеется случайная величина X(x1,x2,x3,x4,x5,x6,x7,x8), имеющая восемь состояний с распределением вероятностей Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа: Это 000, 001, 010, 011, 100, 101, 110, 111 Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию

Определив избыточность L по формуле L=1H/H0=12,75/3=0,084, видим, что возможно сокращение длины кода на 8,4%. Возникает вопрос: возможно ли составить код, в котором на одну букву будет, в среднем приходится меньше элементарных символов. Такие коды существуют. Это коды ШеннонаФано и Хаффмана. Принцип построения оптимальных кодов: 1. Каждый элементарный символ должен переносить максимальное количество информации, для этого необходимо, чтобы элементарные символы (0 и 1) в закодированном тексте встречались в среднем одинаково часто. Энтропия в этом случае будет максимальной. 2. Необходимо буквам первичного алфавита, имеющим большую вероятность, присваивать более короткие кодовые слова вторичного алфавита.

«Цель этого курса - подготовить вас к вашему техническому будущему.»

Привет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2442 в закладки, 394k прочтений)?

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга , написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.

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

Мы уже перевели 28 (из 30) глав. И ведем работу над изданием «в бумаге».

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

Рассмотрев компьютеры и принцип их работы, сейчас мы будем рассматривать вопрос представления информации: как компьютеры представляют информацию, которую мы хотим обработать. Значение любого символа может зависит от способа его обработки, у машины нет никакого определенного смысла у используемого бита. При обсуждении истории программного обеспечения 4 главе мы рассматривали некоторый синтетический язык программирования, в нём код инструкции останова совпадал с кодом других инструкций. Такая ситуация типична для большинства языков, смысл инструкции определяется соответствующей программой.

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

Рисунок 10.1

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим алфавит из небольшого числа символов, обычно алфавиты намного больше. Алфавиты языков начинается от 16 до 36 символов, включая символы в верхнем и нижнем регистре, числа знаки, препинания. Например, в таблице ASCII 128 = 2^7 символов.
Рассмотрим специальный код, состоящий из 4 символов s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Как приёмник должен трактовать следующее полученное выражение

Как s1s1s4 или как s2s4 ?

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

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Декодирует сообщение уникальным способом. Возьмем произвольную строку и рассмотрим, как ее будет декодировать приемник. Вам необходимо построить дерево декодирования Согласно форме на рисунке 10.II. Строка

1101000010011011100010100110 …

Может быть разбита на блоки символов

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Согласно следующему правилу построения дерева декодирования:

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

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

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

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

Рисунок 10.II

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

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Предположим мы получили последовательность 011111...111 . Единственный способ, которым можно декодировать текст сообщения: группировать биты с конца по 3 в группе и выделять группы с ведущим нулем перед единичками, после этого можно декодировать. Такой код декодируемый единственным способом, но не мгновенным! Для декодирования необходимо дождаться окончания передачи! В практике такой подход нивелирует скорость декодирования (теорема Макмиллана), следовательно, необходимо поискать способы мгновенного декодирования.

Рассмотрим два способа кодирования одного и того же символа, Si:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Дерево декодирование этого способа представлено на рисунке 10.III.

Рисунок 10.III

Второй способ

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111 ,

Дерево декодирование это ухода представлены на рисунке 10.IV.

Наиболее очевидным способом измерения качество кода - это средняя длина для некоторого набора сообщений. Для этого необходимо вычислить длину кода каждого символа, помноженную на соответствующую вероятность появления pi. Таким образом получится длина всего кода. Формула средней длины L кода для алфавита из q символов выглядит следующим образом

Где pi - вероятность появления символа si, li - соответствующая длина закодированного символа. Для эффективного кода значение L должно быть как можно меньше. Если P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 и p5 = 1/16, тогда для кода #1 получаем значение длины кода

А для кода #2

Полученные значения говорят о предпочтительности первого кода.
Если у всех слов в алфавите будет одинаковая вероятность возникновения, тогда более предпочтительным будет второй код. Например, при pi = 1/5 длина кода #1

А длина кода #2

Этот результат показывает предпочтительность 2 кода. Таким образом, при разработке «хорошего» кода необходимо учитывать вероятность возникновения символов.

Рисунок 10.IV

Рисунок 10.V

Рассмотрим неравенство Крафта, которое определяет предельное значение длины кода символа li. По базису 2 неравенство представляется в виде

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

Для доказательства неравенства Крафта для любого быстрого уникального декодируемого кода построим дерево декодирования и применим метод математической индукции. Если у дерева есть один или два листа, как показано на рисунке 10.V, тогда без сомнения неравенство верно. Далее, в случае если у дерева есть более чем два листа, то разбиваем дерево длинный m на два поддерева. Согласно принципу индукции предполагаем, что неравенство верно для каждой ветви высотой m -1 или меньше. Согласно принципу индукции, применяя неравенство к каждой ветви. Обозначим длины кодов ветвей K" и K"". При объединении двух ветвей дерева длина каждого возрастает на 1, следовательно, длина кода состоит из сумм K’/2 и K’’/2,

Теорема доказана.

Рассмотрим доказательство теорема Макмиллана. Применим неравенство Крафта к непоточно декодируем кодам. Доказательство построено на том факте, что для любого числа K > 1 n-ая степень числа заведомо больше линейной функции от n, где n - довольно большое число. Возведем неравенство Крафта в n-ую степень и представим выражение в виде суммы

Где Nk число символов длины k, суммирование начинаем с минимальной длины n-го представление символа и заканчиваем максимальной длины nl, где l - максимальная длина закодированного символа. Из требования уникального декодирования следует, что. Сумма представляется в виде

Если K > 1, тогда необходимо n установить довольно большим для того, чтобы неравенство стало ложным. Следовательно, k <= 1; теорема Макмиллана доказана.

Рассмотрим несколько примеров применения неравенство Крафта. Может ли существовать уникально декодируемый код с длинами 1, 3, 3, 3? Да, так как

А что насчёт длин 1, 2, 2, 3? Рассчитаем согласно формуле

Неравенство нарушено! В этом коде слишком много коротких символов.

Точечные коды (comma codes) - это коды, которые состоят из символов 1, оканчивающиеся символом 0, за исключением последнего символа, состоящего из всех единичек. Одним из частных случаев служит код

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5= 11111.

Для этого кода получаем выражение для неравенства Крафта

В этом случае достигаем равенство. Легко видеть, что для точечных кодов неравенство Крафта вырождается в равенство.

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

Необходимо отметить, что неравенство Крафта говорит не о том, что этот код уникально декодируемый, а о том, что существует код с символами такой длины, которые уникальна декодируемый. Для построения уникальной декодируемого кода можно присвоить двоичным числом соответствующую длину в битах li. Например, для длин 2, 2, 3, 3, 4, 4, 4, 4 получаем неравенство Крафта

Следовательно, может существовать такой уникальный декодируемый поточной код.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

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

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

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

Продолжение следует...

Кто хочет помочь с переводом, версткой и изданием книги - пишите в личку или на почту [email protected]

Кстати, мы еще запустили перевод еще одной крутейшей книги -