Декодирование циклических кодов

Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.

011 - ошибка в четвертом разряде

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

010 - ошибка во 2-м контрольном разряде

Существует более общий алгоритм обнаружения и исправления ошибок:

1. Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

2. Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.

3. Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x) и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.

Пример 4.1 Необходимо проверить принятый код 1101110, для g(x)=1011 и t=1.

1. Принятый код 1101110 делим на g(x), находим остаток R(x)=111, w=3

2. Код 1101110 сдвигаем влево на один разряд, получаем 1011101. Делим на образующий многочлен g(x). Находим остаток R(x)=101, вес w=2

3. Снова производим сдвиг влево, получаем 0111011. Делим на g(x). Остаток R(x)=001. w=1

4. Складываем сдвинутую комбинацию с остатком 0111011+001=0111010

5. Производим два циклических сдвига вправо

0111010 -> 0011101 ->1001110

В результате получили исправленную комбинацию.

Блок-схема программы кодера(7,4)

нет да да

Блок-схема программы декодера(7,4)

нет да да

нет да

		Циклический сдвиг влево

нет да да

Листинги программ.

Среда разработки: Code::Blocks 13.2 — свободная кроссплатформенная среда разработки.

Язык программирования С++. Стандарт языка С++11.

Кодер (7,4) циклического кода по регистрам.

#include <iostream>

using namespace std;

int app_coder(int x, int y)

{

//Описание многочленов a и g

int a[4];

int g[4];

int c[3];

//Задание многочленов a и g в виде массивов

for (int i = 0; i < 4; i++)

{

a[3 - i] = x % 10;

g[3 - i] = y % 10;

x = x / 10;

y = y / 10;

}

//Инициализация массива c, содержащего биты сдвигового регистра

for (int i = 0; i < 3; i++)

c[i] = 0;

//Расчёт битов сдвигового регистра

for (int i = 0; i < 4; i++)

{

int k = (c[2] + a[i]) % 2;

if (k==0)

{

c[2] = c[1];

c[1] = c[0];

}

else

{

c[2] = (c[1] + g[2]+1) % 2;

c[1] = (c[0] + g[1]+1) % 2;

}

c[0] = k;

//Вывод входных битов и содержимого сдвигового регистра

cout << a[i] << " ";

for (int j = 0; j < 3; j++)

cout << c[j];

cout << endl;

}

//Вывод частного случая a=0000

int j = 0;

if (a[0] + a[1] + a[2] + a[3] == 0)

cout << "000000";

else

//Вывод нулей в начале сообщения

{

while (a[j] == 0)

{

cout <<a[j];

j++;

}

}

//Формирование выходного сообщения

//Биты сдвигового регистра выводятся в обратном порядке

int k = a[0];

for (int i = 1; i < 4; i++)

k = k * 10 + a[i];

for (int i = 0; i < 3; i++)

k = k * 10 + c[2 - i];

return k;

}

int main()

{

//Образующий многочлен g=1011

const int gpolinom = 1011;

char letter;

int x;

do

{

//Запрос на ввод входного сообщения

cout << "input code message:" << endl;

cin >> x;

//Вывод выходного сообщения

cout << app_coder(x, gpolinom)<<endl;

cout << "One more? (y/n)\n";

cin >> (letter);

}

while (letter == 'y');

return 0;

}

Декодер циклического кода (7,4) по регистрам и весу остатка w<=t.

int app_decoder(int x, int y)

{

//Описание многочленов a и g

char letter;

int a[7];

int b[7];

int g[4];

int c[3];

//Задание многочленов a и g в виде массивов

for (int i = 0; i < 7; i++)

{

a[6 - i] = x % 10;

x = x / 10;

b[6 - i] = a[i];

}

for (int i = 0; i < 4; i++)

{

g[3 - i] = y % 10;

y = y / 10;

}

//Инициализация массива c, содержащего биты сдвигового регистра

for (int i = 0; i < 3; i++)

c[i] = 0;

//Расчёт битов сдвигового регистра

for (int i = 0; i < 7; i++)

{

if (c[2] == 0)

{

c[2] = c[1];

c[1] = c[0];

c[0] = a[i];

}

else

{

c[2] = (c[1] + g[2] + 1) % 2;

c[1] = (c[0] + g[1] + 1) % 2;

c[0] = (a[i] + 1) % 2;

}

//Вывод входных битов и содержимого сдвигового регистра

cout << a[i] << " ";

for (int j = 0; j < 3; j++)

cout << c[j];

cout << endl;

}

//Вычисление веса остатка

int w = c[0] + c[1] + c[2];

cout << "w="<< w << endl;

int count = 0;

//Если ошибки нет – формирование выходного сообщения

if (w == 0)

{

if (a[0] + a[1] + a[2] + a[3] == 0)

cout << "000";

else

{

int j = 0;

while (a[j] == 0)

{

cout << a[j];

j++;

}

}

int k = a[0];

for (int i = 1; i < 4; i++)

k = k * 10 + a[i];

return k;

}

else

{

if (w==1)

//Если вес остатка равен 1, то ошибка в контрольном разряде

for (int i = 4; i < 7; i++)

a[i] = (a[i] + c[6 - i]) % 2;

else

//Если вес остатка больше 1, то ошибка в информационном разряде

{

while (w > 1)

{

cin >> letter;

count++;

//Циклический сдвиг влево

int p = a[0];

for (int i = 0; i < 6; i++)

a[i] = a[i + 1];

a[6] = p;

//Расчёт битов сдвигового регистра

for (int i = 0; i < 3; i++)

c[i] = 0;

for (int i = 0; i < 7; i++)

{

if (c[2] == 0)

{

c[2] = c[1];

c[1] = c[0];

c[0] = a[i];

}

else

{

c[2] = (c[1] + g[2] + 1) % 2;

c[1] = (c[0] + g[1] + 1) % 2;

c[0] = (a[i] + 1) % 2;

}

//Вывод входных битов и содержимого сдвигового регистра

cout << a[i] << " ";

for (int j = 0; j < 3; j++)

cout << c[j];

cout << endl;

}

//Вычисление веса остатка

w = c[0] + c[1] + c[2];

cout << "w=" << w << endl;

}

//Испрвление ошибки

for (int i = 4; i < 7; i++)

a[i] = (a[i] + c[6 - i]) % 2;

//Циклический сдвиг вправо

for (int i = 0; i < count; i++)

{

int p = a[6];

for (int j = 0; j < 6; j++)

a[6 - j] = a[5 - j];

a[0] = p;

}

}

//Формирование исправленного сообщения

if (a[0] + a[1] + a[2] + a[3] == 0)

cout << "000";

else

{

int j = 0;

while (a[j] == 0)

{

cout << a[j];

j++;

}

}

}

int k = a[0];

for (int i = 1; i < 4; i++)

k = k * 10 + a[i];

return k;

}

int main()

{

//Образующий многочлен g=1011

const int gpolinom = 1011;

char letter;

int x;

do

{

//Запрос на ввод входного сообщения

cin >> x;

//Вывод выходного сообщения

cout << app_decoder(x, gpolinom) << endl;

cout << "One more? (y/n)\n";

cin >> letter;

}

while (letter == 'y');

return 0;

}

Не нашли, что искали? Воспользуйтесь поиском: