Построение алгоритма реализации численного метода «быстрой сортировки»

      Например, A=100111001 и B=011011100. Отсюда веса кодовых комбинаций будут равны: V(A)=5, V(B)=5. Кодовая комбинация C=A+B=111100101, вес этой кодовой комбинации равен V(C)=6. Таким образом кодовое расстояние для A и B – d(A,B)=V(C)=6.

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

2. Метод четности / нечетности. Коды Хеминга

      Если  в математическом коде выделен один контрольный разряд, то к каждому двоичному числу добавляется один избыточный разряд. В этот разряд записывается 1 или 0 с таким условием, чтобы сумма цифр по модулю 2 была равна 0 для случая четности или 1 для случая нечетности. Появление ошибки в кодировании обнруживается по нарушению четности / нечетности. При таком кодировании допускается, что может возникнуть только одна ошибка.

      Пример  реализации метода четности:

 

      Можно представить и несколько видоизмененный способ контроля по методу четности / нечетности. Длинное слово разбивается на группы, каждая из которых содержит n разрядов. Контрольные разряды – k, выделяются всем группам по строкам и столбцам согласно следующей схеме:

      

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

      Например: число 1000111011010101110010101 представим по указанной выше схеме, получим:

      Теперь, если при передаче было получено число:

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

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

      При передаче кода может быть искажен  или не искажен любой символ. Если длина кода – n символов, то – полное количество комбинаций кода. По методике Хэмминга можно определить число информационных символов кода, обнаруживающего и корректирующего одиночную ошибку следующим образом:

         

         

       , где 

 – число информационных символов в коде;

 – число контрольных символов;

 – длина кода Хемминга.

      Соотношение n, и для кода Хэмминга можно представить в виде таблицы:

      Таблица 2.2.a

 

      Пусть необходимо передать число 11₁₀=1011₂. Значит . Используя таблицу 2.2.a получаем: , .

      Далее необходимо определить на какой позиции  должны находиться контрольные коэффициенты. Позиция контрольных коэффициентов – k в коде вычисляется по формуле – , где i – порядковый номер коэффициента k. Получаем 7-разрядный код:

      Таблица 2.2.c

 

      Где k_i – контрольный коэффициент (отсчет идет слева на право); И_i – информационный символ (отсчет идет справа на лево).

      Значение  контрольных коэффициентов по правилу: если сумма единиц на проверочных  позициях четная, то значение контрольного коэффициента равно 0, в противном случае – 1. 

      Таблица 2.2.d

 

      Итак, используя таблицу 2.2.d назодим значения контрольных коэффициентов k_i:

      k₁ = 1 + 0 + 1 = 0;

      k₂ = 1 + 1 + 1 = 1;

      k₃ = 0 + 1 +1 = 0.

      Получим код Хемминга 0110011 для передачи числа 11₁₀.

      Теперь  рассмотрим пример корректировки полученного  кодированного в коде Хемминга числа, в котором есть сбой. Получили число 0110001. Для исправления ошибки необходимо определить позицию, в которой произошел сбой. Для этого определяем значения контрольных коэффициентов, используя таблицу 2.2.d:

      k₁ = 0 + 1 + 0 + 1 = 0   – нет ошибки;

      k₂ = 1 + 1 + 0+ 1 = 1   – ошибка;

      k₃ = 0 + 0 +0 + 1 = 1   – ошибка.

     Номер ошибочного разряда совпадает с  суммой позиций контрольных коэффициентов, указавших на наличие ошибки т.е. 2 + 4 = 6. Для  исправления ошибки достаточно инвертировать значение 6-го разряда. 
 

      Задание. Построить код Хемминга для числа А.

      A = 307₁₀ = 100110011₂

      Используя таблицу 2.2.a получаем: , .

 

      k₁ = 1 + 0 + 1 + 1 + 0 + 1 = 0;