Элементы теории кодирования

3. 5. Обнаружение ошибки в кодах Хемминга

        Пусть при  передаче кода β = b₁b₂ …b_l произошла ошибка в разряде с номером t,т. е. на выходе канала получено слово β҆ = b₁b₂… b_t-1b_tb_t+1…b_l.

        Представим t в виде k-разрядного двоичного числа: t = V_k-1…V₁V₀  Покажем, как по коду β҆ найти разряды V_i числа t. Рассмотрим t' = V'_k-1..., V'₁ V'₀ , где:

V'₀ = ⊕∑ b҆_j;  j ϵ L₀ ,

V'₁ = ⊕∑ b҆_j;  j ϵ L₁ ,

…

V'_k-1 = ⊕∑ b҆_j;  j ϵ L _k-1 .

Покажем, что t' = t, т. е. V'_o = V_o; V'₁ = V₁; ...; V'_k-1 = V_k-1. 
Рассмотрим ситуации: 

1. Пусть Vi = 0; это значит, что t не принадлежит L_i = {j ϵ L_i : V_i = 1}. 
Следовательно, все разряды с номерами из L; получены на выходе

канала  без искажения, т.е. b҆_t = b_t, t ϵ L_i. Так как b₂ⁱ  = +∑ b_j; j ϵ L_i, j ≠ 2^j а это равносильно равенству ⊕∑ b = ⊕∑ b҆_j = V'_I = 0 = V_i (j E L_i).

   2. Пусть V_i = 1, тогда t ϵ L_i  ={j ϵ L_i : V_i = 1}, и некоторый раз 
ряд с номером из L_i получен на выходе канала с искажением, т. е. для 
некоторого q из L_t b'_q = b̅_q = b_q ⊕ 1, а для всех j ϵ L_i, j ≠ q, . b҆_j = b_j .

   Отсюда  получаем V'_I  = ⊕∑ b҆_j ( = ⊕∑ b_j ) ⊕1 = 0 ⊕ 1 = 1. Следовательно, и в этом случае V_i = V'_I.

   Пусть в рассмотренной выше задаче ошибка при передаче кодового слова β = b₁b₂b₃b₄b₅b₆b₇b₈b₉b₁₀b₁₁b₁₂b₁₃ = 1010011010111 произошла в 11 разряде (t = 11). Т. е. на выходе канала получено сообщение

   β҆ = b҆₁b҆₂b҆₃b҆₄b҆₅b҆₆b҆₇b҆₈b҆₉b҆₁₀b҆₁₁b҆₁₂b҆₁₃ =  1010011010011

   Для этого кодового сообщения получаем:

V₀ =  b₁ ⊕ b₃ ⊕ b₅ ⊕ b₇ ⊕ b₉ ⊕ b₁₁ ⊕ b₁₃ = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕  0 ⊕ 1 = 1,

V₁ =  b₂ ⊕  b₃ ⊕  b₆  ⊕  b₇ ⊕ b₁₀ ⊕ b₁₁ = 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 = 1,

V₂ =  b₄ ⊕  b₅ ⊕  b₆  ⊕ b₇ ⊕ b₁₂ ⊕ b₁₃ = 0 ⊕ 0 ⊕  1 ⊕ 1 ⊕ 1 ⊕ 1 = 0,

V₃ =  b₈ ⊕  b₉ ⊕  b₁₀  ⊕  b₁₁ ⊕ b₁₂ ⊕ b₁₃ = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕  1 ⊕ 1 = 0.

Таким образом, двоичное представление номера разряда, в котором произошла ошибка, есть 1011. Но это не что иное, как двоичное представление числа 11. Следовательно, ошибочный разряд 11.

3. 6. Декодирование (получение исходного сообщения)

     Этот шаг осуществляется так: после исправления ошибки выписать последовательно слева направо из кода сообщения информационные символы, т. е. а₁а₂...а_т = b₃b₅b₆b₇b₉b₁₀b₁₁b₁₂b₁₃. В нашем примере из кода β = 1010011010111 выписываем α = 101110111. Это и есть исходное сообщение. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

§ 4. Кодирование и обработка чисел компьютером

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

1. Целые положительные числа (целые числа без знака);
2. Целые числа со знаком;
3. Вещественные нормализованные числа.

4. 1. Кодирование в компьютере целых положительных чисел

        Для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Память компьютера имеет байтовую структуру, однако, размер одной адресуемой ячейки обычно составляет несколько байт. В компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов), что называется машинным словом

Машинное  слово –  комбинация связанных соседних ячеек, обрабатываемая совместно

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

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

       Пусть количество разрядов k = 16. При двоичном кодировании число символов p = 2, это 0 и 1. Максимальное число, закодированное  ими равно:

Х_max= 111111111111111₂ – 1

Для определения  самого числа воспользуемся формулой

Х_max=p^k- 1, для k = 16 и  p = 2, получим  Х_max = 2¹⁶- 1 = 65536- 1=65535

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

Минимальным целым числом является число

Х_min = 000000000000000₂ = 0₁₀.

В языках программирования (PASCAL)  для записи целых чисел без знака, отводится 2 байта, и они определены как тип Word. Тип устанавливает способ кодирования числа, количество отводимых для записи ячеек памяти (т.е. разрядность числа), а также перечень допустимых операций при обработке.

        Выход за границу числа 65535 возможен только путем увеличения количества разрядов для записи числа, но это порождает новый тип  кодирования чисел. Если машинное слово занимает 4 бита, что максимальное число, которое будет закодировано,  можно вычислить по той же самой формуле,  и оно будет равно: Х_max =  2147483647.

4. 2. Кодирование в компьютере целых отрицательных чисел

       В вычислительной технике при использовании двоичной системы счисления крайний левый разряд в машинном слове служит для записи знака числа. При  этом условились кодировать:

- знак  плюс или положительное число –  нулем,

- знак  минус или отрицательное число –  единицей.

Такое представление чисел называется прямым кодом.

Под запись самого числа остается 16 - 1=15 двоичных разрядов, что обеспечивает наибольшее значение числа Z_max= 2¹⁵ -  1 = 32767₁₀.

        Данный способ кодирования не является оптимальным. Его применение несколько усложняет порядок обработки чисел. Так, операция сложения двух чисел с разными знаками, по правилу выполнения сложения чисел с разными знаками,  должна быть заменена операцией вычитания меньшего числа из большего числа. Знак полученного  результата  равен знаку заданного  числа, модуль которого больше. Операция сопровождается проверками  условий и выработкой признаков, в соответствии с которыми выбирается то или иное действие.

      Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово на промежутке (0; 65535), сместим положение нуля на середину интервала.

       Числа, попадающие в первую половину (0; 32767) считаются  положительными, а числа из второй половины (32768; 65535) –  отрицательными.

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

      Например, число 100000000000001₂ = 32769₁₀ -  отрицательное числа,

число 000000000000001₂ = 1₁₀ положительное  число.

        Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита –  у кодов положительных чисел его значение “0″ отрицательных – “1″. Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде.

4. 3. Кодирование вещественных нормализованных чисел

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

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