Определение групповых кодов

ГРУППОВЫЕ КОДЫ

Групповые коды принято обозначать в виде двойки (n,m), где n - длина кода, а m - число информационных символов [11]. Тогда число контрольных символов k=n-m.

Комбинацию b группового кода запишем в виде последовательности b=b₁b₂,…,b_m,c₁,c₂,…,c_k, где b₁b₂,…,b_m - информационные разряды, а c₁,c₂,…,c_k - контрольные разряды.

По определению для групповых кодов b_iÅb_j, также комбинация группового кода, т.е. результат поразрядного суммирования комбинации b_i с комбинацией b_j, даст другую комбинацию группового кода. Из этого следует, что кодовое расстояние группового кода определяется (d(b_ib_j)=wb_iÅb_j) весом кодовой комбинации с минимальным числом единиц.

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

Совокупность b₁, b₂, …, b_n кодовых комбинаций называется линейно зависимой, если существует набор элементов a_l, a₂, …, a_n (a_iÎ{0,1}), среди которых хотя бы один отличен от нуля и выполняется условие a_lb₁Åa₂b₂Å…Åa_nb_n=0.

Если это равенство возможно при всех a_i=0, то кодовые комбинации b₁, b₂, …, b_n называются линейно независимыми.

Если среди 2^m кодовых комбинаций группового кода выбрано n линейно независимых кодовых комбинаций b₁, b₂, …, b_m, то для любого набора a_l, a₂, …, a_m (одновременно не равных нулю) получим комбинацию группового кода по правилу

b_r=a_lb₁Åa₂b₂Å…Åa_mb_m¹0. (3.1)

Составляя всевозможные наборы элементов a_l, a₂, …, a_m, число которых равно, можно получить 2^m кодовых комбинаций группового кода по правилу (3.1).

Таким образом, любой набор линейно независимых кодовых комбинаций порождает групповой код (n,m). Такой набор записывается в виде матрицы G_m,n, которая называется образующей или порождающей [17]. Матрицу G_m,n можно привести к канонической форме G_m,n=|I_k,R_m,k|, где I_k – единичная матрица, R_m,k – матрица контрольных элементов.

Образующая матрица имеет вид

Если B_1,m – матрица-строка безызбыточного двоичного кода, то кодовая комбинация группового кода определится в виде произведения

b=B_1,m´G_m,n=|b₁b₂,…,b_m,c₁,c₂,…,c_k|, (3.2)

причем контрольные элементы определятся по формуле

. (3.3)

Из формулы (3.2) следует, что первые m элементов комбинации b группового кода определяются комбинацией безызбыточного кода, а остальные k=n-m элементов определяются как комбинацией безызбыточного кода, так и элементами матрицы R_m,k. Поэтому первые m элементов комбинации b группового кода называются информационными элементами, а остальные k - контрольными.

Уравнение (3.3) задает преобразование m разрядной кодовой комбинации безызбыточного кода в n разрядную кодовую комбинацию группового кода. Так как контрольные символы получаем в результате линейных операций над информационными элементами, то групповой код называют еще линейным.

Пример. Задана образующая матрица

.

Пусть B_1,3 =001. Контрольный элемент c₁ =0x1Å0x1Å1x0=0, контрольный элемент c₂ =0x0Å0x0Å1x1=1, следовательно, кодовая комбинация группового кода b =00101.

Матрицу R_m,k контрольных элементов следует задать исходя из следующих условий:

а) вес каждой строки должен быть не менее d-1;

б) две любые строки должны отличаться друг от друга не менее, чем в d-2 разрядах.

Число контрольных элементов k определяется по формулам Хэмминга [18]:

, d нечетное число; (3.4)

, d нечетное число. (3.5)

Пример. Построить корректирующий код, который будет передавать 34 сообщения и обнаруживать две ошибки.

Число информационных символов кода (формула (1.1)) m=]log₂34[=6. Из формулы (2.1) определяем, что d=3. Из условия (3.4) осуществляет поиск значения k: k=1 – условие 1³log₂(1+7) не выполняется; k=2 – условие 2³log₂(1+8) не выполняется; k=3 – условие 3³log₂(1+9) не выполняется; k=4 – условие 4³log₂(1+10) выполняется.

Построив шестнадцать комбинаций простого кода, выберем любые шесть, удовлетворяющие условиям построения матрицы R_6,4 контрольных элементов.

Получим образующую матрицу группового кода (10,6)

.

Дата добавления: 2014-01-06