Первичное кодирование информации

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

При длине n исходного кода число кодовых слов равно 2n. Следовательно, для кодирования первичным кодом M сообщений необходимо, чтобы M2 ≤n.

Известно, что любое число можно представить с помощью многочлена:

где q – основание системы счисления, q = 2, 3 …;

n – длина кодового слова; i – номер разряда данного числа;

ai – множитель, принимающий любые целочисленные значения от 0 до q-1, показывающий, сколько единиц i-го разряда содержится в числе.

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

Учитывая эти обстоятельства, целесообразно выбирать основания систем счисления q таким образом, чтобы обеспечивалось минимальное значение произведения q ⋅ n (min q ⋅ n) при кодовом представлении (выражении) любого числа.

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

лишь к задаче обнаружения импульса (есть ли импульс или нет) и др.

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

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

Для сохранения достоинств как двоичной, так и десятичной систем счисления используют двоично-десятичные коды с различными весами (весовые коды): 8-4-2-1, 5-1-2-1, 2-4-2-1 и др. Цифры в названии кода обозначают вес единиц в соответствующих двоичных разрядах. Двоично-десятичные коды чаще всего используют как промежуточные коды при вводе в ЭВМ данных, представленных в десятичном коде. Двоично-десятичные коды с весами 5-1-2-1 и 2-4-2-1 широко используются при поразрядном (посимвольном) уравновешивании в измерительной технике. В двоично-десятичном коде каждую цифру десятичного числа записывают в виде четырехразрядного числа.

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

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

Перевод числа из кода Грея в двоичный код выполняется по следующему правилу: первая единица со стороны старших разрядов остается без изменения, а последующие цифры (0 и 1) остаются без изменения, если число единиц, им предшествующих, четно, и инвертируются, если число единиц нечетно.

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

6. Алгоритм шифрования данных DES.

симметричный алгоритм шифрования, разработанный фирмой IBM и утвержденный правительством США в 1977 году как официальный стандарт. DES имеет блоки по 64 бита и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований.

Подробнее. Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T). Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты. Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:

L(i)=R(i-1) R(i) = L(i-1) xor f(R(i-1), K(i)),

Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16). Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP^-1. Матрицы IP^-1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP^-1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP^-1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP^-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.