Коды проверяющие ошибки

	p4	p3	p2	p1
В двоичном представлении	0	1	0	1
В десятичном представлении		4	2	1	Σ = 5

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

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

Код Грея

Код Грея, рефлексный двоичный код — двоичная система нумерования, в которой два соседних значения различаются только в одном двоичном разряде.

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

Название

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

Код получил имя  исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

Применения

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

коды Грея часто  используются в датчиках-энкодерах. Их использование удобно тем, что два соседних значения шкалы сигнала отличаются только в одном разряде. Также они используются для кодирования номера дорожек в жёстких дисках.

Код Грея можно использовать также и для решения задачи о Ханойских башнях .

Широко применяются коды Грея и в теории генетических алгоритмов ^[2] для кодирования генетических признаков, представленных целыми числами.

Преобразование двоичного кода в код Грея

Коды Грея легко  получаются из двоичных чисел путём побитовой операции «Исключающее ИЛИ» с тем же числом, сдвинутым вправо на один бит. Следовательно, i-й бит кода Грея G_i выражается через биты двоичного кода B_i следующим образом:

где   – операция «исключающее ИЛИ»; биты нумеруются справа налево, начиная с младшего.

Ниже приведён алгоритм преобразования из двоичной системы счисления в код Грея, записанный на языке C++:

unsigned int grayencode(unsigned int g)

{

    return g ^ (g >> 1);

}

Тот же самый алгоритм, записанный на языке Паскаль:

function BinToGray(b:integer):integer;

begin

  BinToGray:=b xor (b shr 1)

end;

Преобразование кода Грея в двоичный код

Обратный алгоритм – преобразование кода Грея в двоичный код – можно выразить рекуррентной формулой

причём преобразование осуществляется побитно, начиная со старших разрядов, и значение B_{i + 1}, используемое в формуле, вычисляется на предыдущем шаге алгоритма. Действительно, если подставить в эту формулу вышеприведённое выражение для i-го бита кода Грея, получим

Однако приведённый  алгоритм, связанный с манипуляцией отдельными битами, неудобен для программной реализации, поэтому на практике используют видоизменённый алгоритм:

где N – число битов в коде Грея (для увеличения быстродействия алгоритма в качестве N можно взять номер старшего ненулевого бита кода Грея); знак   означает суммирование при помощи операции «исключающее ИЛИ», то есть

Действительно, подстатавив  в формулу выражение для i-го бита кода Грея, получим

 

Здесь предполагается, что бит, выходящий за рамки разрядной сетки (B_{N + 1}), равен нулю.

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

unsigned int graydecode(unsigned int gray)

{

    unsigned int bin;

    for (bin = 0; gray; gray >>= 1) {

      bin ^= gray;

    }

    return bin;

}

Тот же самый алгоритм, записанный на языке Паскаль:

function GrayToBin(b:integer):integer;

 var g:integer;

begin

  g:=0;

  while b>0 do begin

    g:=g xor b;

    b:=b shr 1;

  end;

  GrayToBin:=g;

end;

Генерация кодов Грея

Ниже представлен  один из алгоритмов создания последовательности кода Грея заданной глубины, записанный на языке Perl:

  my $depth = 16; # generate 16 Gray codes, 4 bits wide each

  my @gray_codes = ( '0', '1' );

  while(scalar(@gray_codes)<$depth)

     {

     my @forward_half=map{'0'.$_} @gray_codes;

     my @reverse_half=map{'1'.$_} reverse(@gray_codes);

     @gray_codes=(@forward_half,@reverse_half);

     } 
 
 
 
 

Рекурсивная функция  построение кода Грея на языке C:

//n -- требуемая длина кода,

//m -- указатель на массив, как минимум, длины n

//     для хранения кода (должен быть выделен до вызова функции)

//depth -- параметр рекурсии

 

int gray (int n, int* m, int depth)

 

{

      int i, t = (1 << (depth - 1));

 

      if (depth == 0)

            m[0] = 0;

 

      else {

        //массив хранит десятичные записи двоичных слов

            for (i = 0; i < t; i++)

                  m[t + i] = m[t - i - 1] + (1 << (depth - 1));

      }

      if (depth != n)

            gray(n, m, depth + 1);

 

      return 0;} 

Турбо Код

Ту́рбо-код — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами.

Турбо-код состоит  из каскада параллельно соединённых систематических кодов. Эти составляющие называются компонентными кодами. В качестве компонентных кодов могут использоваться свёрточные коды, коды Хемминга, Рида — Соломона, Боуза — Чоудхури — Хоквингема и другие. В зависимости от выбора компонентного кода турбо-коды делятся на свёрточные турбо-коды (англ. Turbo Convolutional Codes (ТСС)) и блоковые коды-произведения (англ. Turbo Product Codes (TPC)).^[1]

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

История 

До момента возникновения турбо-кода был широко распространён метод каскадного кодирования, при котором данные кодировались сначала кодом Рида-Соломона, а затем свёрточным кодом. Он достаточно близко подходит к границе Шеннона и объединяет в себе блок коррекции ошибок, использующий код Рида — Соломона и блок свёрточных кодов, декодируемых с помощью алгоритма Витерби.

Турбо-коды были предложены К. Берроу (C. Berrou), А. Главьё (A. Glavieux) и П. Ситимашимой (P. Thitimajshima) (Высшая национальная школа телекоммуникаций, Бретань, Франция (англ.Ecole Nationale Superieure des Telecommunications de Bretagne (ENST))) в 1993 году в статье «Кодирование и декодирование с исправлением ошибок вблизи предела Шеннона: турбо-коды» (англ. 'Near Shannon Limit Error-correcting Coding and Decoding: Turbo-code') ^[2], опубликованной в трудах IEEE. В последующей статье ^[3] Берроу отдаёт должное интуиции Г. Бэттэйла (G. Battail), Дж. Хагенауэра (J. Hagenauer) и П. Хёера (P. Hoeher), которые в конце 1980-х пролили свет на вероятностную обработку данных. Также Берроу упоминает, что Роберт Галлагер (англ.) и М. Таннер (M. Tanner) ещё в своё время представляли методы кодирования и декодирования с общими принципами, очень близкими к турбо-кодам, но в то время не были доступны необходимые вычислительные возможности. 

Кодирование

Рис.1 Общая  структурная схема турбо-кодера

На рис. 1 представлена общая структурная схема M-блочного турбо-кодера.

Сначала на вход формирователя пакетов PAD (англ. Packet Assembler/Disassembler) поступает блок данных U длиной k бит. В формирователе пакетов к данным прибавляется ещё (n − k)дополнительных бит служебной информации, соответствующих используемому стандарту формирования пакета и включающих в себя символы его начала и окончания. То есть получается пакет X₀, состоящий из n бит.

Далее последовательность бит X₀ поступает параллельно на M ветвей, содержащих последовательно соединённые перемежитель и компонентный кодер. Таким образом X₀ используется в качестве входных данных сразу всеми компонентными кодерами.

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

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

Кодовая скорость

Кодовая скорость — отношение длины кодового блока на входе к длине преобразованного кодового блока на выходе кодера.

В отсутствие перфоратора исходная последовательность X₀ мультиплексируется с последовательностями проверочных бит  , образуя кодовое слово, подлежащее передаче по каналу. Тогда значение кодовой скорости на выходе турбо-кодера