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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тексты – это последовательности символов, входящих некоторый алфавит. Кодирование текста сводится к двоичному кодированию алфавита, на основе которого он построен. Чаще всего применяется байтовое кодирование алфавита. В этом случае максимальная мощность алфавита составляет 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 . В этом случае каждому цвету отводят пять разрядов.

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

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

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

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

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

Материал из Википедии - свободной энциклопедии

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

Общие сведения

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

Сжатие данных

Прямая коррекция ошибок

Криптография

Криптография (от др.-греч. κρυπτός - скрытый и γράφω - пишу), это область знаний о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства

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 год В. А. Котельников был также профессором, заведующим кафедрой Московского физико-технического института.

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

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

Формат

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

Программа курса

1. Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова.
2. Неравенство Крафта-Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов.
3. Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.
4. Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки.
5. Коды Варшамова-Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов.
6. Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона, Плоткина.
7. Вложение метрических пространств. Лемма о числе векторов в евклидовом пространстве. Граница Элайеса-Бассалыго.
8. Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова-Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга.
9. Остаточный код. Граница Грайсмера-Соломона-Штиффлера.
10. Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове).
11. Коды Рида-Соломона. Алгоритм декодирования Берлекэмпа-Велча.
12. Коды Рида-Маллера: кодовое расстояние, алгоритм мажоритарного декодирования.
13. Варианты обобщений конструкции Рида-Маллера. Лемма Липтона-ДеМилло-Шварца-Зиппеля. Понятие об алгеброгеометрических кодах.
14. Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера-Спилмана.
15. Теоремы Шеннона для вероятностной модели канали.
16. Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема Мак-Элиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации в задаче MAX-SAT.

Кодирование. Основные понятия.

Различные методы кодирования широко используются в практической деятельности человека с незапамятных времён. Например, десятичная позиционная система счисления – это способ кодирования натуральных чисел. Другой способ кодирования натуральных чисел – римские цифры, причем этот метод более наглядный и естественный, действительно, палец – I, пятерня – V, две пятерни – X. Однако при этом способе кодирования труднее выполнять арифметические операции над большими числами, поэтому он был вытеснен способом кодирования основанном на позиционной десятичной системой счисления. Из этого примера можно заключить, что различные способы кодирования обладают присущими только им специфическими особенностями, которые в зависимости от целей кодирования могут быть как достоинством конкретного способа кодирования, так и его недостатком.

Широко известны способы числового кодирования геометрических объектов и их положения в пространстве: декартовы координаты и полярные координаты. И эти способы кодирования отличаются присущими им специфическими особенностями.

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

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

– оптимальная передача данных по каналам связи;

– защита информации (сообщений) от несанкционированного доступа;

– обеспечение помехоустойчивости при передаче данных по каналам связи;

– сжатие информации.

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

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

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

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

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

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

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

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

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

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

M = a·n. (2.1)

Наибольшее количество различных чисел, которое может быть записано в этом устройстве N :

N = a n .

Прологарифмировав это выражение и выразив из него n получим:

n = ln N / ln a.

Преобразовав выражение (2.1) к виду

M = a ∙ ln N / ln a (2.2)

можно определить, при каком основании логарифмов a количество элементов M будет минимальным при заданном N . Продифференцировав по a функцию M = f(a) и приравняв её производную к нулю, получим:

Очевидно, что для любого конечного a

ln N / ln 2 a ≠ 0

и, следовательно,

ln a - 1 = 0,

откуда a = e ≈ 2,7.

Так как основание системы счисления может быть только целым числом, то а выбирают равным 2 или 3. Для примера зададимся максимальной емкостью устройства хранения N =10 6 чисел. Тогда при различных основаниях систем счисления (а )количество элементов (M )в таком устройстве хранения будет, в соответствии с выражением (2.2), следующие (Таблица 2.1):

Таблица 2.1.

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