Представление чисел в ЭВМ в формате с плавающей запятой.

Такой формат предусматривает представление числа в показательной форме.

Например, десятичное число 685,73₁₀. представляется в виде 0,68573×10³, здесь 0,68573 – мантисса, 10 – основание десятичной системы счисления, 3 – порядок.

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

Кодирование буквально пронизывает информационные технологии [36].

В теории кодирования рассматриваются:

· представление данных произвольной природы в памяти ЭВМ (мы рассмотрели представление чисел);

· обеспечение помехоустойчивости при передаче данных по каналам связи (кодирование по нечетности, по Хэммингу, с использованием циклических полиномов);

· защита данных от несанкционированного доступа (криптографическое кодирование);

· сжатие информации в базах данных.

 

35 Понятие о помехоустойчивом кодировании

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

Простой код – если все его символы используются для представления информации.

Равномерный код – если все его слова имеют одинаковое количество разрядов.

Существуют коды обнаруживающие ошибки и коды, обнаруживающие и исправляющие ошибки.

Как правило, при передаче информации используется избыточность – не все разряды используются для передачи информации, не все 2ⁿ (где n количество разрядов) комбинаций используются для её представления.

Разделяют разрешённые и запрещённые комбинации. Появление запрещённых комбинаций – ошибка передачи информации.

В теории кодирования используется понятие кодового расстояния (расстояние Хэмминга).

d – кодовое расстояние – это число разрядов, по которым отличаются две кодовые комбинации.

В этих двух четырехразрядных кодовых комбинациях d=2.

Рассмотрим двухразрядную информацию.

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

Чтобы обнаружить ошибку необходимо, чтобы выполнялось следующее неравенство:

d_min ³ t +1,

где t – кратность ошибок, а d_min – минимальное кодовое расстояние.

Здесь уже можно обнаружить ошибку, но нельзя её исправить. Исправить ошибку, значит, по виду принятой комбинации установить, какая истинная комбинация передавалась.

Для исправления необходимо: d_min³2t+1 (рис. 83).

Рис. 83. Принцип исправления ошибок

 

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

Рис. 84. Возможные ошибки при передаче трехразрядной информации

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

 

Примеры кодов.

1. Код с проверкой четности.

x2	x2	k

 

где k – контрольный разряд, чтобы сумма единиц была четной, либо нечетной. Это – контроль по четности (нечетности). В настоящее время широко применяется в стандартных микропроцессорах (ранее – только в особо ответственных вычислительных системах, например, военных).

В приемнике формируется контрольный разряд с помощью элемента сложения по модулю 2 (рис. 85).

Рис. 85. Передатчик и приемник информации с контролем по нечетности на основе элементов сложения по модулю 2 с инверсией

 

2. Коды с простым повторением – это коды, в которых повторяется кодовая комбинация.

3. Корреляционные коды.

В таких кодах используются дополнительные символы для представления информации:

0®01

1®10

4. Равновесные коды.

Характеризуются тем, что каждая комбинация содержит одинаковое количество нулей и единиц. Например, 2 из 5:

01100®0

11000®1

10100®2

10010®3

01010®4

00110®5

10001®6

01001®7

00101®8

00011®9

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

 

Помехоустойчивое кодирование по Хэммингу – обеспечивает обнаружение и исправление ошибок при передаче информации (контроль передачи информации).

В кодовом слове всего m разрядов, где m=n+k, n – количество информационных разрядов, k – количество контрольных разрядов.

Используется контроль по нечетности, причем формируется несколько групп контроля по нечетности.

Пример. Передается четырехразрядная информация:

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

В нашем случае: n=4, k=3. Разместим передаваемую информацию в секторах диаграммы Эйлера для трех взаимно пересекающихся множеств А, В, С (рис. 86).

A: k₁=1

B: k₂=1

C: k₃=0

 

 

Рис. 86. Диаграмма Эйлера для кодирования по Хэммингу

четырехразрядной информации

 

Пусть произошла ошибка в разряде х₂ (рис. 87).

 

Рис. 87. Ошибка в разряде х₂

 

Искажение (ошибка) привела к изменению информации и нарушению нечетности в двух контрольных группах А и С. Именно это и укажет на номер искаженного разряда. Каждый сектор («кусочек») диаграммы Эйлера определяет один из разрядов n или k.

Для определения числа контрольного разряда необходимо использовать соотношение m£2^k–1, или n+k£2^k–1.

Далее строится матрица Хэмминга.

1 0 1 0 1 0 1

1 1 0 0 1 1 0

1 1 1 1 0 0 0

x₄ x₃ x₂ k₃ x₁ k₂ k₁

Если дано число информационных разрядов n, то необходимо определить число контрольных разрядов. Выбираются двоичные эквиваленты номеров всех m разрядов (справа налево, младшие разряды вверху). Столбцы с одной единицей отводятся под контрольные разряды. Выделяются три группы контрольных разрядов k₁, k₂, k₃.

В передатчике формируются контрольные разряды по нечётности k₁,k₂,k₃ путём суммирования по модулю 2 соответствующих разрядов.

Записываются уравнения Хэмминга:

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

Синдром ошибки – вектор .

Если искажение не произошло, то синдром нулевой. Если не нулевой он укажет на место ошибки. Если (101), то ошибка в 5-ом столбце, разряд х₂, поскольку этот разряд входит в две группы контроля по нечетности – первую и вторую – это области А и С диаграммы Эйлера (рис. 87).

Иногда реальную информацию передают в другом порядке: отдельно информационные, отдельно контрольные разряды. Представим информацию в матричном виде. Матрица Хэмминга обозначается Н. Информационную подматрицу обозначим Р, а контрольную – I:

Если – входной вектор, – полное кодовое слово, тогда кодирование заключается в следующих матричных операциях:

, где – конкатенация (сцепление) информации в определенном порядке следования разрядов.

На вектор воздействуют ошибки. Используем вектор ошибок :

,

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

.

В матричных операциях используется сумма по модулю 2 (Å). Заметим, что описанный код Хэмминга, позволяет обнаруживать и исправлять только одиночные (однократные) ошибки. Для обнаружения двукратных ошибок вводят еще один контрольный разряд – для всей посылки.