Построить линейный групповой код способный исправлять одиночную ошибку

Задание
1

Построить
линейный групповой код, способный исправлять одиночную ошибку.

Код
предусматривает возможность посылки N = 64  сообщений,
тогда:

; 

nu=6

nk=4

n=nu+nk=10

Построим
производящую матрицу G, она представляется слиянием
матриц И и П.

В качестве И
выбирают единичную матрицу размером nu:

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

Определим вес
строк матрицыП:

WП > = d0 —
1

d0 = 3

Следовательно:
WП  ≥ 2, исходя из этого, составим матрицу
П:

1

1

1

1

1

1

1

0

1

1

0

1

1

0

1

1

0

1

1

1

1

1

0

0

Тогда
производящая матрица будет иметь вид:

1

0

0

0

0

0

1

1

1

1

0

1

0

0

0

0

1

1

1

0

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

0

1

0

1

1

0

0

0

0

1

0

0

1

1

1

0

0

0

0

0

1

1

1

0

0

Задание
2

Привести
пример 10 кодовых комбинаций.

Кодирование сообщений:

1) 19 в
двоичной системе: 010011

Для
определения значения кодовых разрядов сложим по правилам двоичного поля строки
с номерами, соответствующими номерам ненулевых разрядов сообщения:

2 – 1110

5 – 0111

6 – 1100

      0101

Следовательно,
линейный групповой код имеет вид: 0100110101

2) 20 в
двоичной системе: 010100

2 – 1110

4 – 1011

      0101

Линейный
групповой код: 0101000101

3) 35 в
двоичной системе имеет вид: 100011

1 – 1111

5 – 0111

6 – 1100

      0100

Линейный
групповой код: 1000110100

4) 38 в
двоичной системе: 100110

1 – 1111

4 – 1011

5 – 0111

      0011

Линейный
групповой код: 1001100011

5) 44 в
двоичной системе: 101100

1 – 1111

3 – 1101

4 – 1011

                  1001

Линейный
групповой код: 1011001001

6) 47 в
двоичной системе: 101111

1 – 1111

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      0010

Линейный
групповой код: 1011110010

7) 49 в
двоичной системе: 110001

1 – 1111

2 – 1110

6 – 1100

      1101

Линейный
групповой код: 1100011101

8) 55 в
двоичной системе: 110111

1 – 1111

2 – 1110

4 – 1011

5 – 0111

6 – 1100

      0001

Линейный
групповой код: 1101110001

9) 56 в
двоичной системе: 111000

1 – 1111

2 – 1110

3 – 1101

      1100

Линейный
групповой код: 1110001100

10) 63
в двоичной системе: 111111

1 – 1111

2 – 1110

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      1100

Линейный
групповой код: 1111111100

Задание
3

Показать процесс исправления ошибки в заданном разряде k .

Для
исправления одинарной ошибки построим матрицу Н, которая получается путем
транспонирования матрицы П и присоединения к ней единичной матрицы размерностью
nk:

1

2

3

4

5

6

7

8

9

10

1

1

1

1

0

1

1

0

0

0

1

1

1

0

1

1

0

1

0

0

1

1

0

1

1

0

0

0

1

0

1

0

1

1

1

0

0

0

0

1

Покажем процедуру
исправления одиночной ошибки на примере сообщения 60:

Отправленное
сообщение:        1111000111

Принятое сообщение:               
1111001111

т.е. имеется
ошибка в седьмом разряде.

Проведем
проверки:

1)  Для
первой проверки берем P1 и те разряды из
информационной части кода, которые совпадают с ненулевыми разрядами первого
столбца матрицы П:

S1=P1+а1+а2+а3+а4+а6=1+1+1+1+1+0=1

По аналогии
проводим остальные проверки.

2)  S2=P2+а1+а2+а3+а5+а6=1+1+1+1+0+0=0

3)  S3=P3+а1+а2+а4+а5=1+1+1+1+0=0

4)  S4=P4+а1+а3+а4+а5=1+1+1+1+0=0

В результате
получаем вектор S= 1000

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

Источник

Систематические корректирующие коды. Линейно групповой код

Время на прочтение
6 мин

Количество просмотров 8.6K

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

Что из себя представляет корректирующий код. Корректирующий код – это код направленный на обнаружение и исправление ошибок. А систематические коды — Это коды, в которых контрольные и информационные разряды размещаются по определенной системе. Одним из таких примеров может служить Код Хэмминга или собственно линейно групповые коды.
Линейно групповой код состоит из информационных бит и контрольных. Например, для исходной комбинации в 4 символа, линейно групповой код будет выглядеть вот так:

|1100|110|

Где первые 4 символа это наша исходная комбинация, а последние 3 символа это контрольные биты.

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

$d=log(n+1+log(n+1))$

Где n — это число информационных бит, то есть длина исходной комбинации, и log по основанию 2. И общая длина N кода будет вычисляться по формуле:

$N=n+d$

Допустим исходная комбинация будет составлять 10 бит.

$d=log(10+1+log(10+1))$

$d=3,867$

d всегда округляется в

большую сторону

, и d=4.

И полная длина кода будет составлять

14

бит.

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

Производящая матрица, размерностью N на n, где N — это длина линейно группового кода, а n — это длина информационной части линейно группового кода. По факту производящая матрица представляет из себя две матрицы: единичную размерностью m на m, и матрицу контрольных бит размерностью d на n. Если единичная матрица составляется путём расставления единиц по главной диагонали, то составление «контрольной» части матрицы имеет некоторые правила. Проще объяснить на примере. Мы возьмем уже известную нам комбинацию из 10 информационных битов, но добавим коду избыточность, и добавим ему 5-ый контрольный бит. Матрица будет иметь размерность 15 на 10.

1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 1 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 1 0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 1 0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 1

«Контрольная» часть составляется по схеме уменьшения двоичного числа и соблюдения минимального кодового расстояния между строками: в нашем случае это 11111, 11110, 11101…
Минимальное кодовое расстояние для комбинации будет вычисляться по формуле:

Wp=r+s

Где r – это ранг обнаруживаемой ошибки, а s – ранг исправляемой ошибки.
В нашем случае ранг исправляемой и обнаруживаемой ошибки 1.
Также необходимо составить проверочную матрицу. Она составляется путём транспонирования «контрольной» части и после неё добавляется единичная матрица размерности d на d. 

1 1 1 1 1 0 1 1 1 0 1 0 0 0 0
1 1 1 1 0 1 1 1 0 1 0 1 0 0 0
1 1 1 0 1 1 1 0 0 0 0 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 0 0 1 0
1 0 1 1 1 1 0 1 1 1 0 0 0 0 1

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

Рассмотрим этот этап на примере исходного сообщения 1001101010.

Линейно групповой код: 100110101011100

Сразу обозначим, что контрольные разряды в ЛГК определяются по правилам чётности суммы соответствующих индексов, в нашем случае, эти суммы составляют: 5,3,3,4,4. Следовательно, контрольная часть кода выглядит: 11100.

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

Допустим, наш код был отправлен с ошибкой в 6-ом разряде. Для определения ошибок в коде служит, уже ранее составленная проверочная матрица

Для того, чтобы определить, в каком конкретно разряде произошла ошибка, нам необходимо узнать «синдром ошибки». Синдром ошибки вычисляется методом проверок по ненулевым позициям проверочной матрицы на чётность. В нашем случае этих проверок пять, и мы проводим наше полученное сообщение через все эти проверки.

$S1=n1+n2+n3+n4+n5+n7+n8+n9+n11$

$S2=n1+n2+n3+n4+n6+n7+n8+n10+n12$

$S3=n1+n2+n3+n5+n6+n7+n13$

$S4=n1+n2+n4+n5+n6+n9+n10+n14$

$S5=n1+n3+n4+n5+n6+n8+n9+n10+n15$

Получив двоичное число, мы сверяем его со столбцами проверочной матрицы. Как только находим соответствующий «синдром», определяем его индекс, и выполняем инверсию бита по полученному индексу.

В нашем случае синдром равен: 01111, что соответствует 6-му разряду в ЛГК. Мы инвертируем бит и получаем корректный линейно групповой код.

Декодирование скорректированного ЛГК происходит путём простого удаления контрольных бит. После удаления контрольных разрядов ЛГК мы получаем исходную комбинацию, которая была отправлена на кодировку.

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

Реализация работы с ЛГК на C++:

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <cctype>
#include <cmath>
using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");
	cout<<"Производящая матрица:"<<endl;
	int matr [10][15]={{1,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,1,0,0,0,0,0,0,0,0,1,1,1,1,0},{0,0,1,0,0,0,0,0,0,0,1,1,1,0,1},{0,0,0,1,0,0,0,0,0,0,1,1,0,1,1},{0,0,0,0,1,0,0,0,0,0,1,0,1,1,1},
	{0,0,0,0,0,1,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,1,0,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,1,0,0,1,1,0,0,1},{0,0,0,0,0,0,0,0,1,0,1,0,0,1,1},{0,0,0,0,0,0,0,0,0,1,0,1,0,1,1}};
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<15;j++)
		{
			cout<<matr[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<"Проверочная матрица:"<<endl;
	int matr_2 [5][15]={{1,1,1,1,1,0,1,1,1,0,1,0,0,0,0},{1,1,1,1,0,1,1,1,0,1,0,1,0,0,0},{1,1,1,0,1,1,1,0,0,0,0,0,1,0,0},{1,1,0,1,1,1,0,0,1,1,0,0,0,1,0},{1,0,1,1,1,1,0,1,1,1,0,0,0,0,1}};
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<15;j++)
		{
			cout<<matr_2[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<"Введите комбинацию: "<<endl;
	string str;
	bool flag=false;
	while(flag!=true)
	{
		cin>>str;
		if(str.size()!=10)
		{
			cout<<"Недопустимая размерность строки!"<<endl;
			flag=false;
		}
		else
			flag=true;
	}
	vector <int> arr;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]=='1')
			arr.push_back(1);
		else if(str[i]=='0')
			arr.push_back(0);
	}
	cout<<"Ваша комбинация: ";
	for(int i=0;i<arr.size();i++)
		cout<<arr[i];
	cout<<endl;
	vector <int> S;
	
	vector <vector<int>> R;
	for(int i=0;i<10;i++)
	{
		if(arr[i]==1)
		{
			vector <int> T;
			for(int j=0;j<15;j++)
			{
				T.push_back(matr[i][j]);
			}
			R.push_back(T);
		}
	}
	
	cout<<endl;
	cout<<"Суммиирвоание строк для построения группового кода: "<<endl;
	for(vector <vector<int>>::iterator it=R.begin();it!=R.end();it++)
	{
		copy((*it).begin(),(*it).end(),ostream_iterator<int>(cout,"\t"));
		cout<<"\n";
	}
	cout<<endl;
	vector <int> P;
	for(int i=0; i<15;i++)
	{
		int PT=0;
		for(int j=0; j<R.size();j++)
		{
			PT+=R[j][i];
		}
		P.push_back(PT);
	}
	for(int i=10; i<15;i++)
	{
		if(P[i]%2==0)
			P[i]=0;
		else if(P[i]%2!=0)
			P[i]=1;
	}
	cout<<endl<<"Групповой линейный код: "<<endl;
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	int rand_i;
	rand_i=5;
	cout<<endl<<"В сообщении сгенерирована ошибка: ";
	if(P[rand_i]==0)
		P[rand_i]=1;
	else if(P[rand_i]==1)
		P[rand_i]=0;
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	int S1, S2, S3, S4, S5;

	//Проверки на чётность

	S1=P[0]+P[1]+P[2]+P[3]+P[4]+P[6]+P[7]+P[8]+P[10];
	S2=P[0]+P[1]+P[2]+P[3]+P[5]+P[6]+P[7]+P[9]+P[11];
	S3=P[0]+P[1]+P[2]+P[4]+P[5]+P[6]+P[12];
	S4=P[0]+P[1]+P[3]+P[4]+P[5]+P[8]+P[9]+P[13];
	S5=P[0]+P[2]+P[3]+P[4]+P[5]+P[7]+P[8]+P[9]+P[14];

	//Составление синдрома

	if(S1%2==0)
	{
		S1=0;
	}
	else if(S1%2!=0)
	{
		S1=1;
	}

	if(S2%2==0)
	{
		S2=0;
	}
	else if(S2%2!=0)
	{
		S2=1;
	}

	if(S3%2==0)
	{
		S3=0;
	}
	else if(S3%2!=0)
	{
		S3=1;
	}

	if(S4%2==0)
	{
		S4=0;
	}
	else if(S4%2!=0)
	{
		S4=1;
	}
	if(S5%2==0)
	{
		S5=0;
	}
	else if(S5%2!=0)
	{
		S5=1;
	}
	cout<<endl<<"Синдром ошибки: "<<S1<<S2<<S3<<S4<<S5<<endl;
	int mas_s[5]={S1,S2,S3,S4,S5};
	int index_j=0;
	bool flag_s=false;
	for(int i=0;i<15;i++)
	{
		if((matr_2[0][i]==mas_s[0])&&(matr_2[1][i]==mas_s[1])&&(matr_2[2][i]==mas_s[2])&&(matr_2[3][i]==mas_s[3])&&(matr_2[4][i]==mas_s[4]))
		{
			index_j=i;
		}
	}
	cout<<endl<<"Разряд ошибки: "<<index_j+1<<endl;
	if(P[index_j]==0)
		P[index_j]=1;
	else if(P[index_j]==1)
		P[index_j]=0;
	cout<<"Исправленный код: ";
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	cout<<endl;
	P.erase(P.begin()+14);
	P.erase(P.begin()+13);
	P.erase(P.begin()+12);
	P.erase(P.begin()+11);
	P.erase(P.begin()+10);
	cout<<"Исходный код: ";
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	cout<<endl;
	return 0;
}

Источники:

1. StudFiles – файловый архив студентов [Электронный ресурс] studfiles.net/preview/4514583/page:2/.

2. Задачник по теории информации и кодированию [Текст] / В.П. Цымбал. – Изд. объед. «Вища школа», 1976. – 276 с.

3. Тенников, Ф.Е. Теоретические основы информационной техники / Ф.Е. Тенников. – М.: Энергия, 1971. – 424 с.

Источник

Задание
1

Построить
линейный групповой код, способный исправлять одиночную ошибку.

Код
предусматривает возможность посылки N = 64  сообщений,
тогда:

; 

nu=6

nk=4

n=nu+nk=10

Построим
производящую матрицу G, она представляется слиянием
матриц И и П.

В качестве И
выбирают единичную матрицу размером nu:

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

Определим вес
строк матрицыП:

WП > = d0 —
1

d0 = 3

Следовательно:
WП  ≥ 2, исходя из этого, составим матрицу
П:

1

1

1

1

1

1

1

0

1

1

0

1

1

0

1

1

0

1

1

1

1

1

0

0

Тогда
производящая матрица будет иметь вид:

1

0

0

0

0

0

1

1

1

1

0

1

0

0

0

0

1

1

1

0

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

0

1

0

1

1

0

0

0

0

1

0

0

1

1

1

0

0

0

0

0

1

1

1

0

0

Задание
2

Привести
пример 10 кодовых комбинаций.

Кодирование сообщений:

1) 19 в
двоичной системе: 010011

Для
определения значения кодовых разрядов сложим по правилам двоичного поля строки
с номерами, соответствующими номерам ненулевых разрядов сообщения:

2 – 1110

5 – 0111

6 – 1100

      0101

Следовательно,
линейный групповой код имеет вид: 0100110101

2) 20 в
двоичной системе: 010100

2 – 1110

4 – 1011

      0101

Линейный
групповой код: 0101000101

3) 35 в
двоичной системе имеет вид: 100011

1 – 1111

5 – 0111

6 – 1100

      0100

Линейный
групповой код: 1000110100

4) 38 в
двоичной системе: 100110

1 – 1111

4 – 1011

5 – 0111

      0011

Линейный
групповой код: 1001100011

5) 44 в
двоичной системе: 101100

1 – 1111

3 – 1101

4 – 1011

                  1001

Линейный
групповой код: 1011001001

6) 47 в
двоичной системе: 101111

1 – 1111

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      0010

Линейный
групповой код: 1011110010

7) 49 в
двоичной системе: 110001

1 – 1111

2 – 1110

6 – 1100

      1101

Линейный
групповой код: 1100011101

55 в
двоичной системе: 110111

1 – 1111

2 – 1110

4 – 1011

5 – 0111

6 – 1100

      0001

Линейный
групповой код: 1101110001

9) 56 в
двоичной системе: 111000

1 – 1111

2 – 1110

3 – 1101

      1100

Линейный
групповой код: 1110001100

10) 63
в двоичной системе: 111111

1 – 1111

2 – 1110

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      1100

Линейный
групповой код: 1111111100

Задание
3

Показать процесс исправления ошибки в заданном разряде k .

Для
исправления одинарной ошибки построим матрицу Н, которая получается путем
транспонирования матрицы П и присоединения к ней единичной матрицы размерностью
nk:

1

2

3

4

5

6

7

8

9

10

1

1

1

1

0

1

1

0

0

0

1

1

1

0

1

1

0

1

0

0

1

1

0

1

1

0

0

0

1

0

1

0

1

1

1

0

0

0

0

1

Покажем процедуру
исправления одиночной ошибки на примере сообщения 60:

Отправленное
сообщение:        1111000111

Принятое сообщение:               
1111001111

т.е. имеется
ошибка в седьмом разряде.

Проведем
проверки:

1)  Для
первой проверки берем P1 и те разряды из
информационной части кода, которые совпадают с ненулевыми разрядами первого
столбца матрицы П:

S1=P1+а1+а2+а3+а4+а6=1+1+1+1+1+0=1

По аналогии
проводим остальные проверки.

2)  S2=P2+а1+а2+а3+а5+а6=1+1+1+1+0+0=0

3)  S3=P3+а1+а2+а4+а5=1+1+1+1+0=0

4)  S4=P4+а1+а3+а4+а5=1+1+1+1+0=0

В результате
получаем вектор S= 1000

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

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

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

Групповые
коды удобно задавать при помощи матриц,
размерность которых определяется
параметрами k
и n.
Число строк равно k,
а число столбцов равно n
= k+m.

.
(6)

Коды,
порождаемые этими матрицами, называются
(n,
k)-кодами,
а соответствующие им матрицы порождающими
(образующими, производящими). Порождающая
матрица G
состоит
из информационной Ikk
и проверочной Rkm
матриц. Она является сжатым описанием
линейного кода и может быть представлена
в канонической (типовой) форме

.
(7)

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

.
(8)

Строки
единичной матрицы представляют собой
линейно-незави-симые комбинации (базисные
вектора), т. е. их по парное суммирование
по модулю два не приводит к нулевой
строке.

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

Столбцы
добавочной матрицы
Rkm
определяют
правила формирования проверок. Число
единиц в каждой строке добавочной
матрицы должно удовлетворять условию
r1

d0-1,
но число единиц определяет число
сумматоров по модулю 2 в шифраторе и
дешифраторе, и чем их больше, тем сложнее
аппаратура.

Производящая
матрица кода G(7,4)
может иметь вид

и
т.д.

Процесс
кодирования состоит во взаимно —
однозначном соответствии k-разрядных
информационных слов — I
и n-разрядных
кодовых слов — с

c=IG.
(9)

Например:
информационному слову I
=[1
0 1 0] соответствует следующее кодовое
слово

.
(10)

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

Процесс
декодирования состоит в определении
соответствия принятого кодового слова,
переданному информационному. Это
осуществляется с помощью проверочной
матрицы
H(n, k).

,
(11)

где
RmkT
-транспонированная проверочная матрица
(поменять строки на столбцы);
Imm
—
единичная матрица.

Для
(7, 4)- кода проверочная матрица имеет вид

.
(12)

Между
G(n
,k)
и H(n,
k)
существует однозначная связь, т. к. они
определяются в соответствии с правилами
проверки, при этом для любого кодового
слова должно выполняться равенство cHT
=
0.

Строки
проверочной матрицы определяют правила
формирования проверок. Для (7, 4)-кода

p1+a1+a2a4
= S1
;

p2+a1+a2a3
= S2
;
(13)

p3+a1+a3a4
= S3
.

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

Пример
1. Построить
групповой код способный передавать 16
символов первичного алфавита с
исправлением одиночной ошибки. Показать
процесс кодирования, декодирования и
исправления ошибки для передаваемого
информационного слова 1001.

Решение:

  1. Построим
    производящую матрицу G(n,
    k)    .

Если
объем кода N
= 2k
=
16,
то количество информационных разрядов
к
= 4. Минимальное
кодовое расстояние для исправления
одиночной ошибки d0=2s+1=3.
По
заданной длине информационного слова,
используя соотношения:

n
= k+m, 2n
(n+1)2k
и 2m
n+1

вычислим
основные параметры кода n
и m.

m=[log2
{(k+1)+
[log2(k+1)]}]=[log2
{(4+1)+
[log2(4+1)]}]=3.

Откуда
n
= 7,
т. е. необходимо построить (7, 4)-код.

В
качестве информационной матрицы Ik(7,
4) —
выбираем единичную матрицу (44), а в
качестве проверочной матрицы Rkm(7
,4) —
выбираем матрицу (43), каждая строка
которой содержит число единиц больше
или равно двум (r1
d0-1).

Таким
образом, в качестве производящей можно
принять матрицу

.

2.
Определим комбинации корректирующего
кода.

Для
заданного числа информационных разрядов
k
= 4,число
кодовых комбинаций равно N
= 2k
=
24
=
16.

1)
0000 5) 0010 9) 0001 13) 0011

2)
1000 6) 1010 10) 1001 14) 1011

3)
0100 7) 0110 11) 0101 15) 0111

4)
1100 1110 12) 1101 16) 1111

Старшинство
разрядов принимаем слева на право, в
соответствии с их поступлением на вход
декодера.

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

Например,
для информационного слова I=
[1001] кодовое слово имеет вид

.

Передаваемые
в канал кодовые комбинации имеют вид:

1)
0000 000 5) 0010 110 9) 0001 101 13) 0011 011

2)
1000 111 6) 1010 001 10) 1001 010 14) 1011 100

3)
0100 011 7) 0110 101 11) 0101 110 15) 0111 000

4)
1100 100 1110 010 12) 1101 101 16) 1111 111

Процесс
декодирования состоит в определении
соответствия принятого кодового слова,
переданному информационному и
осуществляется с помощью проверочной
матрицы H(7,
4).

Для
построенного (7, 4)-кода проверочная
матрица имеет вид

.

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

Пусть
в процессе передачи произошла ошибка
во 2-м информационном разряде 1 1 0 1 1 0 0 1

В
соответствии с проверочной матрицей
составляем проверочные векторы

p1a1a2a4
=S1
= 0110 = 0;

p2a1a2a3
=S2
=
0111 = 1 ;

p3a1a3a4
=S3
= 1101 = 1.

Синдром
011 показывает, что ошибка произошла во
2-м информационном разряде, который
необходимо проинвертировать.

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

Решение:
Объем кода равен N
= 2k.
При
100 сообщениях: 100
N 2k
, откуда k
= 7.
По заданной длине информационного
слова, используя соотношения:

n
= k+m, 2n
(n+1)2k
и 2m
n+1

вычислим
основные параметры кода n
и m.

m=[log2
{(k+1)+
[log2(k+1)]}]=[log2
{(7+1)+
[log2(7+1)]}]=4.

Откуда
n
= 11, т.
е. получили (11, 7)-код.

В
качестве информационной матрицы выбираем
единичную матрицу I(7×7).Проверочная
матрица содержит 4 столбца и 7 строк,
которые содержат r1
d0-1
единиц в четырехразрядном коде (2, 3,
4-единицы).

.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

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

Понятие группы

Определение. Группой называется совокупность элементов, для которой определена некоторая бинарная операция и выполняются следующие четыре аксиомы!

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

Аксиома ассоциативности. Если выбранная операция есть вложение, то для любых трех элементов с группы справедливо соотношение

Если выбранная операция есть умножение, то для любых трех элементов и с группы справедливо соотношение

Аксиома единичного элемента. В группе существует единственный единичный элемент. Если выбранная операция есть сложение, то

единичный элемент обозначается как 0 и определяется соотношением

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

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

Если выбранная операция есть умножение, то элемент, обратный элементу а, обозначается и определяется соотношением

Определение. Группа называется аддитивной, если в качестве операции группы используется операция сложения.

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

Определение. Группа, состоящая из конечного числа элементов, называется конечной.

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

Пример. Задано множество Над элементами множества определена операция суммы. Выяснить, является множество , с введенной операцией, групиой.

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

Проверка аксиомы вамкнутости:

Результат операции всегда является элементом группы, следовательно, аксиома вамкнутости выполняется.

Проверка аксиомы ассоциативности;

Результаты операции не аависят от места расположения скобок. Следовательно, аксиома ассоциативности выполняется.

Проверка аксиомы единичного элемента.

Очевидно, единичным элементом является 0, так как

т. е. выполняется соотношение для единичного элемента.

Проверка аксиомы обратного элемента.

Для каждого элемента множества существует единственный обратный элемент. Любой элемент множества является обратным по отношению к самому себе, так выполняется соотношение

Представляется возможность показать самостоятельно справедливость следующих утверждений:

1. Множество с операцией суммы по модулю 2 является группой.

2. Множество с операцией суммы по модулю 2 является группой.

Понятно линейного группового кода

Определение. Линейным групповым кодом называется конечная аддитивная коммутативная группа элементами которой являются двоичные векторы, в качестве операции группы выбрана операция суммы по модулю 2.

Линейные групповые коды могут быть заданы двумя способами

перечислением векторов;

матричным представлением.

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

Определение. Линейно-независимыми двоичными векторами о называются векторы, для которых выполняется соотношение

где — скаляры, знак операции суммы по модулю 2.

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

Рассмотрим матрицу

Векторы, принадлежащие этой матрице, — линейно-независимы, т. е. матрица является порождающей матрицей некоторого кода Остальные векторы получаются суммированием векторов из порождающей матрицы. Пронумеруем векторы порождающей матрицы сверху вниз в порядке возрастания номеров. Тогда все векторы кода имеют

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

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

где — единичная матрица информационных разрядов линейного кода формата к (как было показано выше, такая матрица порождает натуральный двоичный код длины k); Р — матрица проверочных разрядов линейного кода, содержащая столбцов и к строк.

Так как единичная матрица порождает натуральный двоичный код длины мощность которого равна 2, то ее формат в матрице

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

Пусть линейный групповой код задан своей порождающей матрицей

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

Минимальное расстояние линейного группового кода может быть определено в соответствии со следующим простым алгоритмом:

1. Выписать все векторы линейного группового кода.

2. Для каждого ненулевого вектора найти его вес в смысле Хэмминга. Минимальный вес ненулевого вектора и равен

Справедливость алгоритма вытекает из принадлежности нулевого вектора линейному групповому коду. Действительно, расстояние в смысле Хэмминга между нулевым вектором и вектором с минимальным числом единиц определяет рассматриваемого кода.

В соответствии с рассмотренным алгоритмом определим кода

Так как минимальный вес в смысле Хэмминга то код имеет и позволяет обнаруживать ошибки кратностью корректировать ошибки кратностью Действительно, для обнаружения -кратных ошибок должно выполняться условие или Для коррекции -кратных ошибок должно выполняться условие

Порождающую матрицу группового линейного кода длины о информационными разрядами можно построить, руководствуясь следующими правилами:

1. Все векторы порождающей матрицы должны быть различны и линейно-независимы.

2. Нулевой вектор не должен входить в число векторов порождающей матрицы.

3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга

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

Проверочная часть порождающей матрицы (матрица Р) строится в соответствии со следующими правилами:

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

2 Вес проверочною вектора 4, являющегося суммой по модулю 2 двух любых проверочных векторов, должен удовлетворять

соотношению

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

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

1. Если Р — требуемая мощность линейного кода то формат информационной части его порождающей матрицы равен где

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

3. Каждый вектор порождающей матрицы должен иметь вес в смысле Хэмминга

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

5. Для проверки правильности получения кода по построенной порождающей матрице следует выписать все векторы и определить полученного кода.

Построим порождающую матрицу линейного кода мощностью 16 и обнаруживающей способностью

Так как то и формат единичной части порождающей матрицы линейного кода Порождающая матрица может быть записана в виде

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

Таблица 13.3

Таблица 13.4

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

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

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

матрицы следующим образом!

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

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

Декодирование линейных групповых кодов

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

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

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

некоторого вектора линейного кода удовлетворяет соотношению где — знак операции «сумма mod 2»; — значение соответствующих проверочных разрядов векторов порождающей матрицы из проверочного столбца, соответствующего символу при условии, что пробегает только те значения из , которые соответствуют складываемым векторам порождающей матрицы. Так как каждый проверочный столбец порождающей матрицы образуется как сумма некоторых информационных ее столбцов, а каждый информационный столбец содержит только одну единицу, то справедливо соотношение

или

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

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

Построим уравнения декодирования для линейных кодов, заданных порождающими матрицами и

Уравнение для матрицы строим следующим образом. Проверочный столбец, отмеченный символом содержит единицы для позиций Так как на пересечении строки с и информационного столбца и на пересечении строки и информационного столбца имеются единицы, то уравнение для примет вид Аналогично, получаем все уравнения декодирования для кода, представленного матрицей

и уравнения декодирования для кода, представленного матрицей

В силу справедливости преобразования перепишем уравнения несколько иначе

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

Выявление необнаруживаемых линейными кодами ошибок

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

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

только одну единичную компоненту. Очевидно, матрица имеет вид

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

найдем значение вектора синдрома для каждого из векторов одиночных ошибок. Для этого подставим каждый вектор одиночной ошибки из матрицы в уравнения декорирования линейного кода. Получаемые векторы синдрома допишем в матрицу

Очевидно, матрица в окончательном виде может быть построена формально следующим образом:

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

значение синдромов для случая искажения проверочных разрядов описывается единичной матрицей формата Иными словами, матрица имеет вид

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

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

Как следует из матрицы М, рассматриваемый линейный код обнаруживает все двухкратные ошибки, так как каждому вектору двухкратной ошибки соответствует ненулевой синдром. Матрицы ошибок большей кратности строятся аналогично (например, для получения матрицы описывающей трехкратные ошибки, необходимо найти все суммы из трех векторов однократной ошибки и синдромы). Очевидно, код не обнаруживает трехкратные ошибки, возникающие в разрядах т. е. четыре трехкратные ошибки из 20 возможных. Код не обнаруживает четырехкратные, ошибки, возникающие в разрядах т. е. четыре четырехкратные ошибки из 15 возможных. Код обнаруживает любую пятикратную и шестикратную ошибки. Следовательно, из всех возможных 63 различных ошибок рассмотренный код не обнаруживает только 8 ошибок.

Тривиальные линейные групповые коды

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

их декодирования представляет собой сумму по модулю 2 всех разрядов вектора кода и известна как свертка по модулю 2.

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

Уравнение декодирования единственное и имеет вид

Очевидно, проверочный разряд каждого вектора такого кода принимает единичное значение в случае, если число единиц в информационном векторе нечетно.

Исправление ошибок с помощью линейных групповых кодов

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

исправляющего однократные ошибки, матрица однократных ошибок имеет вид

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

Коды с простым повторением

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

Пример. Построить коде простым повторением мощности 8, Порождающая матрица С такого кода имеет вид

Уравнения, определяющие процедуру декодирования, имеют вид

Очевидно, декодирование кода с простым повторением сводится к сравнению проверочных и информационных разрядов.

Коды с малой плотностью проверок на четность

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

где — единичная матрица формата — длина кода; — число информационных разрядов, а каждая строка матрицы D есть проверочный столбец порождающей матрицы

Пример. По заданной порождающей матрице построить проверочную матрицу .

Очевидно, матрица может быть представлена в виде

Коды с малой плотностью проверок на четность обычно обозначаются как где длина кода; — число информационных разрядов; число единиц в каждой строке матрицы Н.

Условие существования такого кода с можно сформулировать следующим образом:

1. Каждая из строк матрицы Н содержит единиц.

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

Из первого условия следует, что общее количество единиц в матрице Н должно удовлетворять соотношению Общее количество единиц в матрице очевидно, равно

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

Полученное неравенство является верхней границей для Если то к . Иными словами, количество проверочных разрядов по крайней мере в два раза превышает число информационных.

Построим код о малой плотностью проверок на четность при условии, что Используя условие

Следовательно, Общее число единиц в матрице D определяется выражением Очевидно, матрица Я (один из вариантов) может быть представлена в виде

Отсюда порождающая матрица имеет вид

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

матрице и представлены в виде

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

Что из себя представляет из себя корректирующий код. Корректирующий код – это код направленный на обнаружение и исправление ошибок. А систематические коды — Это коды, в которых контрольные и информационные разряды размещаются по определенной системе. Одним из таких примеров может служить Код Хэмминга или собственно линейно групповые коды.
Линейно групповой код состоит из информационных бит и контрольных. Например, для исходной комбинации в 4 символа, линейно групповой код будет выглядеть вот так:

|1100|110|

Где первые 4 символа это наша исходная комбинация, а последние 3 символа это контрольные биты.

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

$$display$$d=log(n+1+log(n+1))$$display$$

Где n — это число информационных бит, то есть длина исходной комбинации, и log по основанию 2. И общая длина N кода будет вычисляться по формуле:

$$display$$N=n+d$$display$$

Допустим исходная комбинация будет составлять 10 бит.

$$display$$d=log(10+1+log(10+1))$$display$$

$$display$$d=3,867$$display$$

d всегда округляется в большую сторону, и d=4.

И полная длина кода будет составлять 14 бит.

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

Производящая матрица, размерностью N на n, где N — это длина линейно группового кода, а n — это длина информационной части линейно группового кода. По факту производящая матрица представляет из себя две матрицы: единичную размерностью m на m, и матрицу контрольных бит размерностью d на n. Если единичная матрица составляется путём расставления единиц по главной диагонали, то составление «контрольной» части матрицы имеет некоторые правила. Проще объяснить на примере. Мы возьмем уже известную нам комбинацию из 10 информационных битов, но добавим коду избыточность, и добавим ему 5-ый контрольный бит. Матрица будет иметь размерность 15 на 10.

1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 1 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 1 0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 1 0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 1

«Контрольная» часть составляется по схеме уменьшения двоичного числа и соблюдения минимального кодового расстояния между строками: в нашем случае это 11111, 11110, 11101…
Минимальное кодовое расстояние для комбинации будет вычисляться по формуле:

Wp=r+s

Где r – это ранг обнаруживаемой ошибки, а s – ранг исправляемой ошибки.
В нашем случае ранг исправляемой и обнаруживаемой ошибки 1.
Также необходимо составить проверочную матрицу. Она составляется путём транспонирования «контрольной» части и после неё добавляется единичная матрица размерности d на d. 

1 1 1 1 1 0 1 1 1 0 1 0 0 0 0
1 1 1 1 0 1 1 1 0 1 0 1 0 0 0
1 1 1 0 1 1 1 0 0 0 0 0 1 0 0
1 1 0 1 1 1 0 0 1 1 0 0 0 1 0
1 0 1 1 1 1 0 1 1 1 0 0 0 0 1

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

Рассмотрим этот этап на примере исходного сообщения 1001101010.

Линейно групповой код: 100110101011100

Сразу обозначим, что контрольные разряды в ЛГК определяются по правилам чётности суммы соответствующих индексов, в нашем случае, эти суммы составляют: 5,3,3,4,4. Следовательно, контрольная часть кода выглядит: 11100.

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

Допустим, наш код был отправлен с ошибкой в 6-ом разряде. Для определения ошибок в коде служит, уже ранее составленная проверочная матрица

Для того, чтобы определить, в каком конкретно разряде произошла ошибка, нам необходимо узнать «синдром ошибки». Синдром ошибки вычисляется методом проверок по ненулевым позициям проверочной матрицы на чётность. В нашем случае этих проверок пять, и мы проводим наше полученное сообщение через все эти проверки.

$$display$$S1=n1+n2+n3+n4+n5+n7+n8+n9+n11$$display$$

$$display$$S2=n1+n2+n3+n4+n6+n7+n8+n10+n12$$display$$

$$display$$S3=n1+n2+n3+n5+n6+n7+n13$$display$$

$$display$$S4=n1+n2+n4+n5+n6+n9+n10+n14$$display$$

$$display$$S5=n1+n3+n4+n5+n6+n8+n9+n10+n15$$display$$

Получив двоичное число, мы сверяем его со столбцами проверочной матрицы. Как только находим соответствующий «синдром», определяем его индекс, и выполняем инверсию бита по полученному индексу.

В нашем случае синдром равен: 01111, что соответствует 6-му разряду в ЛГК. Мы инвертируем бит и получаем корректный линейно групповой код.

Декодирование скорректированного ЛГК происходит путём простого удаления контрольных бит. После удаления контрольных разрядов ЛГК мы получаем исходную комбинацию, которая была отправлена на кодировку.

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

Реализация работы с ЛГК на C++:

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <cctype>
#include <cmath>
using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");
	cout<<"Производящая матрица:"<<endl;
	int matr [10][15]={{1,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,1,0,0,0,0,0,0,0,0,1,1,1,1,0},{0,0,1,0,0,0,0,0,0,0,1,1,1,0,1},{0,0,0,1,0,0,0,0,0,0,1,1,0,1,1},{0,0,0,0,1,0,0,0,0,0,1,0,1,1,1},
	{0,0,0,0,0,1,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,1,0,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,1,0,0,1,1,0,0,1},{0,0,0,0,0,0,0,0,1,0,1,0,0,1,1},{0,0,0,0,0,0,0,0,0,1,0,1,0,1,1}};
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<15;j++)
		{
			cout<<matr[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<"Проверочная матрица:"<<endl;
	int matr_2 [5][15]={{1,1,1,1,1,0,1,1,1,0,1,0,0,0,0},{1,1,1,1,0,1,1,1,0,1,0,1,0,0,0},{1,1,1,0,1,1,1,0,0,0,0,0,1,0,0},{1,1,0,1,1,1,0,0,1,1,0,0,0,1,0},{1,0,1,1,1,1,0,1,1,1,0,0,0,0,1}};
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<15;j++)
		{
			cout<<matr_2[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<"Введите комбинацию: "<<endl;
	string str;
	bool flag=false;
	while(flag!=true)
	{
		cin>>str;
		if(str.size()!=10)
		{
			cout<<"Недопустимая размерность строки!"<<endl;
			flag=false;
		}
		else
			flag=true;
	}
	vector <int> arr;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]=='1')
			arr.push_back(1);
		else if(str[i]=='0')
			arr.push_back(0);
	}
	cout<<"Ваша комбинация: ";
	for(int i=0;i<arr.size();i++)
		cout<<arr[i];
	cout<<endl;
	vector <int> S;
	
	vector <vector<int>> R;
	for(int i=0;i<10;i++)
	{
		if(arr[i]==1)
		{
			vector <int> T;
			for(int j=0;j<15;j++)
			{
				T.push_back(matr[i][j]);
			}
			R.push_back(T);
		}
	}
	
	cout<<endl;
	cout<<"Суммиирвоание строк для построения группового кода: "<<endl;
	for(vector <vector<int>>::iterator it=R.begin();it!=R.end();it++)
	{
		copy((*it).begin(),(*it).end(),ostream_iterator<int>(cout,"t"));
		cout<<"n";
	}
	cout<<endl;
	vector <int> P;
	for(int i=0; i<15;i++)
	{
		int PT=0;
		for(int j=0; j<R.size();j++)
		{
			PT+=R[j][i];
		}
		P.push_back(PT);
	}
	for(int i=10; i<15;i++)
	{
		if(P[i]%2==0)
			P[i]=0;
		else if(P[i]%2!=0)
			P[i]=1;
	}
	cout<<endl<<"Групповой линейный код: "<<endl;
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	int rand_i;
	rand_i=5;
	cout<<endl<<"В сообщении сгенерирована ошибка: ";
	if(P[rand_i]==0)
		P[rand_i]=1;
	else if(P[rand_i]==1)
		P[rand_i]=0;
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	int S1, S2, S3, S4, S5;

	//Проверки на чётность

	S1=P[0]+P[1]+P[2]+P[3]+P[4]+P[6]+P[7]+P[8]+P[10];
	S2=P[0]+P[1]+P[2]+P[3]+P[5]+P[6]+P[7]+P[9]+P[11];
	S3=P[0]+P[1]+P[2]+P[4]+P[5]+P[6]+P[12];
	S4=P[0]+P[1]+P[3]+P[4]+P[5]+P[8]+P[9]+P[13];
	S5=P[0]+P[2]+P[3]+P[4]+P[5]+P[7]+P[8]+P[9]+P[14];

	//Составление синдрома

	if(S1%2==0)
	{
		S1=0;
	}
	else if(S1%2!=0)
	{
		S1=1;
	}

	if(S2%2==0)
	{
		S2=0;
	}
	else if(S2%2!=0)
	{
		S2=1;
	}

	if(S3%2==0)
	{
		S3=0;
	}
	else if(S3%2!=0)
	{
		S3=1;
	}

	if(S4%2==0)
	{
		S4=0;
	}
	else if(S4%2!=0)
	{
		S4=1;
	}
	if(S5%2==0)
	{
		S5=0;
	}
	else if(S5%2!=0)
	{
		S5=1;
	}
	cout<<endl<<"Синдром ошибки: "<<S1<<S2<<S3<<S4<<S5<<endl;
	int mas_s[5]={S1,S2,S3,S4,S5};
	int index_j=0;
	bool flag_s=false;
	for(int i=0;i<15;i++)
	{
		if((matr_2[0][i]==mas_s[0])&&(matr_2[1][i]==mas_s[1])&&(matr_2[2][i]==mas_s[2])&&(matr_2[3][i]==mas_s[3])&&(matr_2[4][i]==mas_s[4]))
		{
			index_j=i;
		}
	}
	cout<<endl<<"Разряд ошибки: "<<index_j+1<<endl;
	if(P[index_j]==0)
		P[index_j]=1;
	else if(P[index_j]==1)
		P[index_j]=0;
	cout<<"Исправленный код: ";
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	cout<<endl;
	P.erase(P.begin()+14);
	P.erase(P.begin()+13);
	P.erase(P.begin()+12);
	P.erase(P.begin()+11);
	P.erase(P.begin()+10);
	cout<<"Исходный код: ";
	for(int i=0; i<P.size();i++)
	{
		cout<<P[i]<<' ';
	}
	cout<<endl;
	return 0;
}

Источники:

1. StudFiles – файловый архив студентов [Электронный ресурс] studfiles.net/preview/4514583/page:2/.

2. Задачник по теории информации и кодированию [Текст] / В.П. Цымбал. – Изд. объед. «Вища школа», 1976. – 276 с.

3. Тенников, Ф.Е. Теоретические основы информационной техники / Ф.Е. Тенников. – М.: Энергия, 1971. – 424 с.

Автор: lFeater

Источник

Источник

Помогаю со студенческими работами здесь

Задача по теории информации. измерение информации
Ребятушки!Помогите, пожалуйста!
Сколько информации о X1 содержится в д.с.в. , Z=(X1+1)^2-X2+X3,…

Написать программу, которая реализует основные операции теории множеств
Написать программу, которая реализует основные операции теории множеств, а именно, объединения,…

Написать программу, которая реализует основные операции теории множеств
Написать программу, которая реализует основные
операции теории множеств, а именно, объединения,…

Написать программу ввода информации по студенту
Написать программу ввода информации по студенту (Ф.И.О.,
группа, факультет, курс) и вывода её на…

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

1

Источник

Понравилась статья? Поделить с друзьями:
  • Постоянно совершаю глупые ошибки
  • Построить код хэмминга для проверки многократных ошибок
  • Посудомоечная машина ariston ошибка a11
  • Построительзапроса отбор добавить ошибка
  • Постоянно разные ошибки синего экрана