10. ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ
10.1. Понятие о кодировании
Кодирование занимает ключевую роль в информатике [36]. Наскаль-ные рисунки первобытных людей – первые попытки кодирования. Между ними и письменностью – дистанция огромного размера. Затем были предметные знаки: забор – символ собственности, корона – символ власти. Идеографическое письмо – картинно-изобразительное письмо – среднее между рисунком и знаковым письмом. Иероглифическое письмо – каждый иероглиф – слово или даже целое понятие. Это письмо сохранилось до сих пор в некоторых странах. Затем появилось письменность, кодирующая уже не непосредственную действительность, а речь. Буквы кодируют звуки, их меньше, чем иероглифов. Иероглифы, буквы, звуки, запахи, жесты, математические обозначения и т.д. – все это знаки. Имеется специальная наука об осмысленных знаковых системах – семиотика. Исследованиями знаковых систем, в которых используются символы алфавитов занимается математическая лингвистика, о которой будет идти речь далее.
Следует отметить, что генетический код, записанный в молекулах ДНК, мы носим с собой. Он передан нам предками, и мы передаем его потомкам – в грядущее.
10.2. Системы счисления, как основа различных кодов
Кодирование информации о численности чего-либо привело к созда-нию систем счисления [36].
Десятичная система счисления – способ кодирования натуральных чисел, причем основание системы счисления проистекало от количества пальцев на руках. История знает и другие системы – двадцатеричная – по числу пальцев на руках и ногах. Римские цифры – другой, более наглядный способ. Один палец – I, пятерня – V, две пятерни – Х, пятьдесят – L, сто – С, тысяча – М. С помощью букв обозначали цифры и греки, и русские, и грузины. Индийцы и арабы придумали нуль и позиционную систему счисления.
Основной единицей кодирования информации в настоящее время яв-ляется бит – один двоичный разряд, который может быть либо нулем (0), либо единицей (1). Подавляющее большинство ЭВМ используют двоичное представление информации. В начале эры компьютеров битами кодировали числа и команды. Потом оказалось, что такое кодирование пригодно для записи, хранения и переработки практически любой информации: изображений (видеоинформации), звука, музыки, фильмов и т.д.
Группы в три бита называют триадами, группы из четырех битов – тетрады. Наиболее часто сейчас говорят о байтах – группах из восьми бит. Два байта – это уже слово. Килобайт – это 210 бит – 1024 бита. Мегабайт – это 220 бит. Гигабайт – это 230 бит. Терабайт – это 240.
Двоичная система счисления.
В двоичной системе счисления основание 2: используется только два символа: 0,1. Поэтому арифметика очень простая: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (0 и перенос в следующий разряд). Запись 11011,101 неко-торого двоичного числа соответствует следующему десятичному числу: 1•24+ 1•23+0•22+ 1•21+ 1•20, 1•2-1+0•2-2+1•2-3=27,625.
Такое представление числа называется представлением с фиксированной запятой. Запятая фиксирована в соответствующей аппаратуре (арифметико-логическом устройстве АЛУ). Часто числа представлялись в виде дробей, поэтому как исходные данные, так и результаты решения задач должны были представляться именно так. Для этого проводили масштабирование – выбирали масштабные коэффициенты. Неправильный выбор масштабных коэффициентов мог вызвать так называемое переполнение разрядной сетки – ошибку в виде образования целой части, для которой в разрядной сетке нет места, и она теряется.
Рассмотрим, как выполняется двоичное суммирование:
Пусть необходимо сложить два двоичных числа 101 и 11:
Двоичное вычитание, например, (10-6 в десятичном коде) выглядит следующим образом:
Для выполнения такой операции необходим специальный «вычита-тель», поэтому вычитание заменяют сложением числа в так называемом обратном коде, когда разряды вычитаемого инверсируют:
При этом образуется перенос 1, который необходимо сложить с про-межуточным результатом 0011:
таким образом, получаем ответ 0100 (10-6=4 в десятичном коде).
Для операций в обратном коде необходим специальный сумматор с так называемым циклическим переносом, обеспечивающим сложение переноса с промежуточным результатом. Это неудобно, поэтому применяют так называемый дополнительный код, который устраняет циклический перенос. Представим десятичное число –6 в двоичном до-полнительном коде (то есть, заменяем операцию 10-6 на операцию 10+ (–6), числа здесь в десятичном коде): –6 десятичное это –0110 двоичное, в обратном коде 1001, да еще прибавляем единицу (таковы правила образования дополнительного кода):
таким образом, дополнительный двоичный код десятичного числа –6 равен 1010. Здесь старший подчеркнутый разряд это знак, знаковый разряд. Тогда операция вычитания выглядит так:
перенос, возникающий в этом случае, просто отбрасывается, получаем 0100 (4 десятичное). Поэтому при аппаратной реализации вычитания может быть использован обычный сумматор.
Дополнительные коды четырехразрядных двоичных чисел показаны в табл. 65.
Таблица 65
Дополнительные коды
0000 0
0001 + 1
0010 + 2
0011 + 3
0100 + 4
0101 + 5
0110 + 6
0111 + 7
1000 Не использ.
1001 - 7
1010 - 6
1011 - 5
1100 - 4
1101 - 3
1110 - 2
1111 - 1
Таким образом, в формате из четырех разрядов представимы числа в диапазоне –7+7 (23 -1).
При использовании байта с фиксированной запятой представляют це-лые числа в диапазоне –127+127 (27 –1).
В общем случае n бит могут кодировать 2n объектов.
Перевод чисел из десятичной в двоичную систему счисления выпол-няют, например, путем деления на основание системы счисления – 2, и записывают соответствующие остатки, либо подбирают соответствующие степени числа 2.
Пример. Дано десятичное число 38, ближайшая степень числа 2 – это число 32, т.е. 25, остается еще 6, ближайшая степень числа 2 – это 4, т.е. 22, остается 2, это 21. Таким образом:
0×27+0×26+1×25+0×24+0×23+1×22+1×21+0×20=100110.
Восьмеричная система счисления.
В восьмеричном коде восемь символов:
0 (000 двоичное),
1 (001 двоичное),
2 (010 двоичное),
3 (011 двоичное),
4 (100 двоичное),
5 (101 двоичное),
6 (110 двоичное),
7 (111 двоичное).
Для перевода числа из восьмеричного кода в двоичный, необходимо каждую цифру восьмеричного кода заменить на триаду (три символа) двоичного, например, 3548=11 101 1002, здесь двоичное число представлено в байтовом формате, поэтому старшая триада неполная. Наоборот, из двоичного кода в восьмеричный: 10 111 1012=2758.
Шестнадцатеричная система счисления.
В шестнадцатеричном коде шестнадцать символов:
0 (0000 двоичное),
1 (0001 двоичное),
2 (0010 двоичное),
3 (0011 двоичное),
4 (0100 двоичное),
5 (0101 двоичное),
6 (0110 двоичное),
7 (0111 двоичное),
8 (1000 двоичное),
9 (1001 двоичное),
A (1010 двоичное),
B (1011 двоичное),
C (1100 двоичное),
D (1101 двоичное),
E (1110 двоичное),
F (1111 двоичное).
Для перевода числа из двоичной системы счисления в шестнадцате-ричную, необходимо заменить каждую тетраду (четыре символа) соответствующим шестнадцатеричным символом, например:
1011 11012 =BD16.
Наоборот, из шестнадцатеричного кода в двоичный:
9АEF16= 1001 1010 1110 11112.
В восьмеричном и шестнадцатеричном кодах можно строить соответ-ствующие арифметики.
Например, в шестнадцатеричном коде: EF16+AC16=19B16 (F+C=1B, 1 переносится в следующий разряд; E+A=18, да еще +1 из предыдущего разряда =19).
В восьмеричном коде: 378+218=608.
Представление чисел в ЭВМ в двоично-кодированном десятичном формате (BCD или десятичном).
В BCD-формате десятичные цифры хранятся в виде 4-битных двоич-ных эквивалентов. В упакованном BCD-формате цепочка десятичных цифр хранится в виде последовательности 4-битных групп, например: 9502 в виде 1001 0101 0000 0010.
В неупакованном BCD-формате каждая цифра хранится в младшей тетраде соответствующего байта.
Представление чисел в ЭВМ в формате с плавающей запятой.
Такой формат предусматривает представление числа в показательной форме.
Например, десятичное число 685,7310. представляется в виде 0,68573103, здесь 0,68573 – мантисса, 10 – основание десятичной системы счисления, 3 – порядок.
В ячейке памяти двоичные числа в формате с плавающей запятой хранятся в виде двух групп цифр: первая группа, называемая мантиссой, определяет само число, вторая, называемая порядком, определяет место запятой в числе. Соответствующим выбором значения порядка можно добиться, чтобы старший разряд мантиссы не был равен нулю. Такая форма называется нормальной, а соответствующая операция приведения к такой форме называется нормализацией.
Кодирование буквально пронизывает информационные технологии [36].
В теории кодирования рассматриваются:
• представление данных произвольной природы в памяти ЭВМ (мы рассмотрели представление чисел);
• обеспечение помехоустойчивости при передаче данных по каналам связи (кодирование по нечетности, по Хэммингу, с использованием цик-лических полиномов);
• защита данных от несанкционированного доступа (криптографическое кодирование);
• сжатие информации в базах данных.
10.3. Понятие о помехоустойчивом кодировании
Код – это совокупность символов в представлении информации. Каждому знаку соответствует определённая комбинация нулей и единиц (бинарное кодирование).
Простой код – если все его символы используются для представления информации.
Равномерный код – если все его слова имеют одинаковое количество разрядов.
Существуют коды обнаруживающие ошибки и коды, обнаруживающие и исправляющие ошибки.
Как правило, при передаче информации используется избыточность – не все разряды используются для передачи информации, не все 2n (где n количество разрядов) комбинаций используются для её представления.
Разделяют разрешённые и запрещённые комбинации. Появление за-прещённых комбинаций – ошибка передачи информации.
В теории кодирования используется понятие кодового расстояния (расстояние Хэмминга).
d – кодовое расстояние – это число разрядов, по которым отличаются две кодовые комбинации.
В этих двух четырехразрядных кодовых комбинациях d=2.
Рассмотрим двухразрядную информацию.
При различных ошибках (типа инверсии разряда) можно получить различные комбинации, причём они входят в исходное множество комбинаций. Поэтому по виду комбинации нельзя обнаружить ошибку. Необходимо, чтобы при возникновении ошибки полученные коды не входили в число используемых.
Чтобы обнаружить ошибку необходимо, чтобы выполнялось следую-щее неравенство:
dmin t +1,
где t – кратность ошибок, а dmin – минимальное кодовое расстояние.
Здесь уже можно обнаружить ошибку, но нельзя её исправить. Исправить ошибку, значит, по виду принятой комбинации установить, какая истинная комбинация передавалась.
Для исправления необходимо: dmin2t+1 (рис. 83).
Рис. 83. Принцип исправления ошибок
От каждой из четырех комбинаций, указанных на рис. 83, ошибочная комбинация с t-кратной ошибкой отличается в t разрядах, поэтому необходимо, чтобы сами ошибочные комбинации отличались друг от друга хотя бы в одном разряде, иначе восстановить передаваемую информацию невозможно. Например, рис. 84 иллюстрирует возможные ошибки при передаче трехразрядной информации.
Рис. 84. Возможные ошибки при передаче трехразрядной информации
и некоторые кодовые расстояния
Примеры кодов.
1. Код с проверкой четности.
x2 x2 k
0 0 1
0 1 0
1 0 0
1 1 1
где k – контрольный разряд, чтобы сумма единиц была четной, либо не-четной. Это – контроль по четности (нечетности). В настоящее время широко применяется в стандартных микропроцессорах (ранее – только в особо ответственных вычислительных системах, например, военных).
В приемнике формируется контрольный разряд с помощью элемента сложения по модулю 2 (рис. 85).
Рис. 85. Передатчик и приемник информации с контролем по нечетности на основе элементов сложения по модулю 2 с инверсией
2. Коды с простым повторением – это коды, в которых повторяется кодовая комбинация.
3. Корреляционные коды.
В таких кодах используются дополнительные символы для представ-ления информации:
001
110
4. Равновесные коды.
Характеризуются тем, что каждая комбинация содержит одинаковое количество нулей и единиц. Например, 2 из 5:
011000
110001
101002
100103
010104
001105
100016
010017
001018
000119
Существуют также систематические коды, где контрольные разряды отделены от информационных. К ним относятся коды Хэмминга.
10.4. Кодирование по Хэммингу
В ряде случаев для контроля функционирования схем реализации ПФ используют прямое сравнение, т.е. сравнивают реакции на схемах. Кроме того, применяются: прямое дублирование со сравнением результатов, троирование.
В своё время широко применялся контроль по модулю, эффективный при арифметических операциях. Используются классы эквивалентностей чисел по модулю.
|1|5=|6|5=|11|5 – сравнимы по модулю.
Контроль по нечётности – это контроль по модулю 2.
Коды Хэмминга – это кодирование с использованием нескольких групп контроля по модулю 2.
Помехоустойчивое кодирование по Хэммингу – обеспечивает обнаружение и исправление ошибок при передаче информации (контроль передачи информации).
В кодовом слове всего m разрядов, где m=n+k, n – количество информационных разрядов, k – количество контрольных разрядов.
Используется контроль по нечетности, причем формируется несколько групп контроля по нечетности.
Пример. Передается четырехразрядная информация:
Количество контрольных разрядов должно быть таковым, чтобы можно было закодировать как информационные разряды, так и сами контрольные.
В нашем случае: n=4, k=3. Разместим передаваемую информацию в секторах диаграммы Эйлера для трех взаимно пересекающихся множеств А, В, С (рис. 86).
A: k1=1
B: k2=1
C: k3=0
Рис. 86. Диаграмма Эйлера для кодирования по Хэммингу
четырехразрядной информации
Пусть произошла ошибка в разряде х2 (рис. 87).
Рис. 87. Ошибка в разряде х2
Искажение (ошибка) привела к изменению информации и нарушению нечетности в двух контрольных группах А и С. Именно это и укажет на номер искаженного разряда. Каждый сектор («кусочек») диаграммы Эйлера определяет один из разрядов n или k.
Для определения числа контрольного разряда необходимо использо-вать соотношение m2k–1, или n+k2k–1.
Далее строится матрица Хэмминга.
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 1 0 0 0
x4 x3 x2 k3 x1 k2 k1
Если дано число информационных разрядов n, то необходимо определить число контрольных разрядов. Выбираются двоичные эквиваленты номеров всех m разрядов (справа налево, младшие разряды вверху). Столбцы с одной единицей отводятся под контрольные разряды. Выделяются три группы контрольных разрядов k1, k2, k3.
В передатчике формируются контрольные разряды по нечётности k1,k2,k3 путём суммирования по модулю 2 соответствующих разрядов.
Записываются уравнения Хэмминга:
Уравнения синдрома ошибки включают и сами контрольные разряды, которые тоже могут исказиться.
Синдром ошибки – вектор .
Если искажение не произошло, то синдром нулевой. Если не нулевой он укажет на место ошибки. Если (101), то ошибка в 5-ом столбце, разряд х2, поскольку этот разряд входит в две группы контроля по нечетности – первую и вторую – это области А и С диаграммы Эйлера (рис. 87).
Иногда реальную информацию передают в другом порядке: отдельно информационные, отдельно контрольные разряды. Представим информацию в матричном виде. Матрица Хэмминга обозначается Н. Информационную подматрицу обозначим Р, а контрольную – I:
Если – входной вектор, – полное кодовое слово, тогда кодирование заключается в следующих матричных операциях:
, где – конкатенация (сцепление) информации в опреде-ленном порядке следования разрядов.
На вектор воздействуют ошибки. Используем вектор ошибок :
,
где – вектор ошибки, указывающий, какие разряды исказились. Тогда получение синдрома ошибки выглядит так:
.
В матричных операциях используется сумма по модулю 2 (). Заме-тим, что описанный код Хэмминга, позволяет обнаруживать и исправлять только одиночные (однократные) ошибки. Для обнаружения двукратных ошибок вводят еще один контрольный разряд – для всей посылки.
10.5. Кодирование с использованием циклических кодов
и математического аппарата умножения и деления полиномов.
Сигнатурный анализ
Циклический код.
Циклический код обязан своим названием особенности: если некото-рая кодовая комбинация принадлежит множеству разрешённых комбинаций, то и комбинация, полученная циклической перестановкой разрядов тоже принадлежит множеству разрешённых комбинаций.
Существует соответствующий математический аппарат умножения и деления полиномов, основным понятием которого является полином, на-пример, третьей степени:
G(x3)=x3+x+1.
Циклические коды позволяют обнаружить не только одиночные, но и групповые ошибки. Такие коды используются при тестировании цифро-вой аппаратуры, чтобы обнаружить отказы в схемах и при криптографической защите информации.
Идея построения циклического кода основана на понятии неприводи-мого многочлена, который делится только на себя и на единицу:
G(x2)=x2+x+1;
G(x)=x+1;
G(x16)=x16+x9+x7+x4+1.
По существу, используется так называемое поле Галуа – алгебра с двумя операциями: умножением и сложением по модулю 2 (GF(2)).
Умножение полиномов.
Некоторый полином x3+1 можно записать в развёрнутой форме:
Здесь коэффициенты принимают значения из бинарного множества.
Умножение производится по правилам обычной алгебры, например:
(х3+1)х=х4+х, т.е. получили:
Это сдвиг на один разряд вправо.
С учетом использования операции сложения по модулю 2, одинако-вые разряды при сложении уничтожаются.
Рассмотрим пример умножения информационного полинома А=х3+1 на порождающий (образующий) полином G=х3+х+1.
Аналитически процесс умножения можно представить так:
Процесс умножения в развернутом виде показан в табл. 66.
Таблица 66
Умножение A на образующий полином G
х6 х5 х4 х3 х2 х 1
А1 х3 1
Аx х4 х
Аx3 х6 х3
АG х6 х4 х 1
Проведем умножение в двоичном коде:
х6пр х5пр х4пр х3пр х2пр хпр 1пр – порядок следования разрядов произведения (пр).
Получим уравнения для произведения многочленов, при условии, что множитель G «жестко задан», а полином А – любой, – степени три:
Амн=х3мн х2мн хмн 1мн – это переменные множимого (мн)-полинома
третьей степени.
G= 1 0 1 1 – множитель (образующий полином).
Процесс умножения в развернутом виде показан в табл. 67.
Таблица 67
0
х3мн
0
х2мн
х3мн
0
хмн х3мн
х2мн
0
1мн х2мн
хмн
0
хмн
1мн
1мн
х3мн
х2мн
х3мн Å хмн
х3мн Åх2мн Å1мн
х3мн Å хмн
хмн Å1мн
1мн
Умножение A на образующий полином G
х6пр х5пр х4пр х3пр х2пр хпр 1пр
Т.е. уравнения, описывающие значения разрядов произведения, в зависимости от значения разрядов множимого при условии «жестко заданного» множителя имеют вид:
Эти уравнения позволяют определить вид соответствующего устройства – умножителя полиномов, основанного на D-триггерах и элементах сложения по модулю 2.
Деление полиномов.
По аналогии с умножением вводится операция деления полиномов.
При делении необходима операция вычитания по модулю 2, однако результат этой операции совпадает с результатом суммы по модулю 2.
Например:
Здесь используется суммирование по модулю 2, поэтому х6+х6=0, аналогично х4+х4=0, х3+х3=0, х+х=0, 1+1=0.
Деление полиномов можно выполнять последовательными вычита-ниями по модулю 2.
Можно показать, что если А – делимое (дл), G – делитель, то разряды частного (чст) определяются так:
1чст=х3длÅх5длÅх6дл
хчст=х4длÅх6дл
х2чст=х5дл
х3чст=х6дл
Остаток:
1ост=1длÅх3длÅх5длÅх6дл
хост=хдлÅх3длÅх4длÅх5дл
х2ост=х2длÅх4длÅх5длÅх6дл
Нулевой остаток указывает на отсутствие ошибки. Такие уравнения позволяют построить схемы – делители на образующий полином.
Принципы контроля передачи информации.
Принцип 1.
Перед передачей информации канал связи исходящего полинома ум-ножается на образующий полином (AG = K).
В канале связи на произведение К воздействует вектор ошибок Е: КÅЕ=К*.
В приёмнике выполняется деление: К*/G=A*. Если остаток нулевой, то ошибки нет, и принятое слово А* – это достоверная информация, а если остаток не равен нулю, то информацию использовать нельзя.
По виду остатка можно определить и вид ошибки.
Принцип 2.
Передаётся сам полином и следом – остаток от деления его на обра-зующий полином.
А||R, R=A/G, где || – операция конкатенации (соединения).
Потом остатки сравниваются, – если они равны, то информацию можно использовать далее.
Имеются циклические коды, которые позволяют обнаружить:
1) одиночные ошибки;
2) групповые ошибки.
Существуют коды БЧХ, Файра для обнаружения групповых ошибок [14].
Кодеры, декодеры, использующие эти принципы, применяются для записи информации на магнитные и оптические диски. Узлы умножения и деления полиномов широко используются при криптографической за-щите данных. Дело в том, что информация, умноженная на образующий полином, может быть расшифрована только, если злоумышленник знает этот полином.
Сигнатурный анализ.
Сигнатура в переводе с латинского – подпись, запись. Это некоторый код, получение которого позволяет судить о работоспособности цифровых схем.
Используется при анализе работоспособности цифровых схем.
Чтобы получить сигнатуру работоспособной схемы для заданного вида отказа, нужно последовательность ее выходных сигналов, представляющую некоторый полином, разделить на образующий полином. При этом получится некоторый остаток от деления, который гораздо короче выходного полинома схемы. Этот остаток и есть сигнатура, которая для работоспособной схемы одна, а для схемы с отказом – другая. Путем определения сигнатур с помощью устройств – сигнатурных анализаторов, использующих узлы умножения и деления полиномов, определяют место отказа. Такой принцип используется в микропроцессорах при проверке работоспособности схем управления после включения питания. Узел имеет отказ, если входная сигнатура правильная, а выходная нет.
10.6. Понятие о криптографической защите информации
Шифрование – это кодирование данных с целью их защиты от несанкционированного доступа [26, 36]. Для этого применяют специальные шифры. Область знаний о шифрах и методах их создания и раскрытия называется криптографией (тайнописью). Свойство шифра противостоять раскрытию называется криптостойкостью. Если раскрытие шифра стоит больше, чем сама зашифрованная информация, то шифр считается надежным. Криптография известна с глубокой древности.
Для шифрования могут использоваться алгоритмы поразрядного сложения по модулю 2 соответствующей двоичной информации с так называемым секретным ключом-секретным двоичным набором. Этот ключ знает отправитель и получатель. Дешифрация производится таким же поразрядным сложением полученной зашифрованной двоичной информации. Такое кодирование называется кодированием с закрытым ключом.
Для шифрования могут также использоваться алгоритмы и узлы умножения и деления полиномов: если полином достаточно сложен, то выходной код имеет исключительно отдаленное сходство с истинным кодом. Это тоже кодирование с закрытым ключом.
В настоящее время производительность компьютеров достигла такой величины, что можно «взломать» закрытые ключи, т.е. подобрать соответствующие кодовые комбинации и расшифровать конфиденциальную информацию. Поэтому сейчас переходят на так называемые алгоритмы шифрования с открытым ключом, строящиеся на основе простых чисел, т.е. чисел, которые делятся без остатка только на себя и на единицу.
Открытый ключ (public key) известен всем, он не зашифрован. Сооб-щение шифруется с помощью открытого ключа. Для дешифрации же ну-жен еще и закрытый ключ (private key), который знают только отправитель и получатель. Это как два ключа для двери: один для закрытия – он есть у всех, другой для открытия, который есть только у «хозяина». Чтобы вычислить закрытый ключ, необходимо произвести разложение на множители очень большого числа (более 100 десятичных цифр). Сейчас это требует годы работы суперкомпьютеров! Хотя подбор простого числа в 100 десятичных цифр (для получения открытого ключа) занимает всего лишь минуты.
Схема кодирования с открытым ключом обратима – сообщение шиф-руется закрытым ключом, а расшифровывается открытым. То есть можно подтвердить личность отправителя, ведь послать сообщение может только обладатель секретного, закрытого ключа. Зато прочитать его может кто угодно, ведь открытый ключ известен всем. На этом основано построение так называемой электронной подписи, удостоверяющей личность отправителя.
10.7. Понятие о сжатии информации
В теории кодирования рассматривают сжатие без потери информации и сжатие с потерей информации, когда эта потеря несущественна, то есть когда потерянной информацией можно пренебречь [26, 36]. В настоящее время для кодирования буквенно-цифровой информации применяют так называемый американский стандартный код ASCII, когда используется байт, например, для кодирования каждой буквы или символа. В обычном тексте частота появления букв различная. Поэтому для сжатия текста можно закодировать часто встречающиеся символы более короткой по-следовательностью битов (менее 8), а редко встречающиеся символы мо-гут кодироваться и более чем восемью битами. Кроме того, в обычном тексте, как правило, встречается менее чем 28=256 символов. Если кодировать не буквы, а слова, то двумя байтами можно закодировать 216=65536 слов. Этого более чем достаточно, ведь, как правило, в слове больше двух букв. Сейчас переходят на двухбайтное кодирование.
При сжатии информации учитывают также наличие нескольких одинаковых подряд следующих байтов, которые могут повторяться многократно. Так при сжатии видеоинформации, например, цвет голубого неба на картине повторяется многократно. В тексте часто повторяются последовательности байтов, например, пробелы.
На учете этих факторов основаны алгоритмы группового кодирования.
Более сложные алгоритмы сжатия строятся на основе замены уже встречавшихся ранее в последовательности, одинаковых групп символов – триадами, каждая из которых содержит: указатель на группу, длину совпадающей группы и первый отличающийся символ, идущий за группой.