Курс лекций по вычислительной технике

       

Для контроля хранения и передачи информации используются


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

     Способность кода обнаруживать или исправлять ошибки  определяется т.н. минимальным кодовым расстоянием. Вообще говоря, кодовое  расстояние - это то минимальное количество разрядов, на которое различаются два любых кода одинаковой разрядности. Для двоичных N-разрядных  неизбыточных  кодов кодовое расстояние - от D мин = 1 до N. В коде Грея =1.

Для избыточных кодов Dмин>1.

Если Dмин=2, то любые два кодовых слова отличаются по крайней мере двумя разрядами. Т.е. одиночная ошибка приведет к появлению недопустимого слова и может быть обнаружена. Если  Dмин=3,  то  одиночная  ошибка приведет к недопустимому слову,  отличающемуся  от  правильного  одним разрядом, а от любого другого на два разряда. Заменяя ошибочное  слово на ближайшее к нему (по кодовому расстоянию), мы исправляем  одиночную ошибку.

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

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

               Код с исправлением одиночной ошибки

                (код Хемминга).

Единичные ошибки в передаче информации исправляет  код  Хемминга.

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

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

     Пусть информационная часть занимает М разрядов, число контрольных разрядов - К. Тогда общее число разрядов N = М+К и должно  соблюдаться соотношение:

             2k-1>= N   или  2k>= M + K + 1



Количество кодов в К - разрядном числе равно 2k. Из них не нулевых 2k-1 .                                                  


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

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

Максимальный номер ошибки в N-разрядном коде тоже N.    

Количество кодов К-разрядном числе 2К, из них ненулевых 2К-1

Мы видим, что как код ошибки, так и номер ошибочного разряда  является «К» разрядным числом. Чтобы ни совпадали  необходимо  выполнить два условия:

1) в качестве номеров контрольных разрядов  следует  выбирать  такие номера, значение которых есть степень двойки.

2) группы разбить таким образом: чтобы двоичный  номер разряда  в группе содержал единицу в том разряде,  который  является  контрольным для этой группы.

                     Рассмотрим пример.

Пусть число информационных разрядов равно 8-и. Если число контрольных разрядов выбрать К=3, то 23 = 8, а М+К+1= 8 +3 +1 =12   8 < 12, что мало. При К=4   24

= 16, а М+К+1= 8+4+1; 16 > 13; то есть 4-х разрядов достаточно. В качестве контрольных разрядов выбираем 1-й=20 ; 2-й = 21 ; 4-й = 22 ; 8-й = 23 .               

         





N



12



11



10



9



8



7



6



5



4



3



2



1



К











К4









К3





К2



К1



М



8



7



6



5





4



3



2





1





к1 -  контрольный разряд для  разрядов

 1 = 0001; 3 = 0011; 5 = 0101; 7 = 0111; 9 = 1001; 11 = 1011

К1= [1] (+) [3] (+) [5] (+) [7] (+) [9] (+) [11]

к2 - контрольный разряд для  разрядов

 2 = 0010; 3 = 0011; 6 = 0110; 7 = 0111; 10 = 1010; 11 = 1011

 к3 - контрольный разряд для  разрядов

         4 = 0100; 5 = 0101; 6 = 0110; 7 = 0111; 12 = 1100

 к4 - контрольный разряд для  разрядов

         8 = 1000; 9 = 1001; 10 = 1010; 11 = 1011; 12 = 1100

     Т.о., если ошибка была в 7-ом разряде, то

           к1 = к2 = к3 = 1, к4 = 0;



          если в 8-ом

          к1 = к2 = к3 = 0; к4 = 1

  

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

     Если же ошибка будет сразу в двух разрядах (1 и  2),  то  получим код 0011, который будет свидетельствовать о наличии  ошибки в 3-м, что неверно.

Если объединить возможности кода контроля по четности  с  возможностями кода Хэмминга (добавив еще один разряд  контроля  по  четности всех разрядов), получим код, который будет исправлять одну ошибку и обнаруживать две:



Контрольный

разряд



Разряд

Чётности



Результат



Нули



0



Ошибок нет



Нули



1



Ошибка разряда чётности



Не нули



0



Двойная ошибка



Не нули



1



Одиночная ошибка

  

 Для 16-разрядного кода число контрольных разрядов равно = 5.

      2^5 >= 16 + 5 + 1; 32 > 21

     Т.о. с ростом числа информационных разрядов доля контрольных  разрядов сокращается.

                              

      4. Принципы функционирования компьютеров

 


Содержание раздела