Кодер Декодер БЧХ

Написати мовою С++ програму, що реалізує алгоритм роботи циклічного кодера та декодера для коду БЧХ, .Писати в консолі 1. Функція кодування зчитує число у двійковому вигляді та виводить закодоване повідомлення у двійковому вигляді. Параметри коду БЧХ задаються у середині програми. Відповідно до цих даних вибрати мінімальний по розміру беззнаковий цілий тип. 2. Функція декодування зчитує закодоване повідомлення у двійковому вигляді, і зчитує у двійковому виді маску з “1” у спотворюваних розрядах, за допомогою якої здійснює інверсію розрядів закодованого повідомлення . Результат декодування виводить. Механізм виявлення та виправлення помилок реалізувати за допомогою алгоритму з циклічними зсувами. Усю необхідну додаткову інформацію виводити у вікно.

У вхідних даних коду БХЧ: n – довжина закодованого повідомлення, s – кількість помилок, що виправляються, P(x) – твірний поліном. Кількість контрольних бітів визначається із залежності: n = k + m, а запис твірного полінома, представленого у вигляді вісімкових цифр, перетворюється шляхом переводу кожної вісімкової цифри у двійкове число. Наприклад, P(x) = 2467. Цифрі 2 відповідає двійкове число 010, цифрі 4 – 100, цифрі 6 – 110, а цифрі 7 – 111, і остаточно – 10100110111 ( x^10 + x^8 + x^5 + x^4 + x^2 + x +1 ).д

параметри циклічного коду : n = 63; k = 57; s = 1; P(x) = 103

А зміг би написати цей кодер декодер бчх ? Просто проблема в тому що я сам покишо неможу цього написати ... А мені просто ну дуже потрібно . Міжіншим ось оригінал завдання в .doc .

http://slil.ru/27752332

RE:

P.S. Потрохи розбираюся у поставленій задачі.

Дуже вам вдячний ...

Міжіншим ось оригінал завдання: http://slil.ru/27752332 . Тут є деякі підказки та приклади ...

Я надіслав модуль з поліномами на EMAIL.

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

type
  float=real;
  polynomial=^term;
  term=record
         degree:integer;
         coefficient:float;
         next:polynomial;
  end;

...

function product_poly(p,q:polynomial):polynomial;
var p_run,q_run,s:polynomial; t:term;
begin
  s:=nil; t.next:=nil; p_run:=copy_poly(p);
  while p_runnil do begin
    q_run:=copy_poly(q);
    while q_runnil do begin
      t.degree:=p_run^.degree+q_run^.degree;
      t.coefficient:=p_run^.coefficient*q_run^.coefficient;
      insert_term(t,true,s); q_run:=q_run^.next;
    end; p_run:=p_run^.next;
  end; product_poly:=s;
end;

По суті можна просто множити поліноми як масиви, а не як списки, а цей алгоритм на сайті вже є і реалізован на Сі.

http://beloshenko.e-hosting.com.ua/forum/494/1357_...

Продовжимо прості логічні міркування.

Схема множення поліномів вже якась є, залишилось лише перекласти на Сі. Поцікавимось питанням кодування. Як отримати закодований поліном? На це питання відповідь дає Вікіпедія. Кодовий поліном c(x) отримується з інформаційного полінома m(x) шляхом домноження(1) на поліном g(x).

(1) c(x)=m(x)*g(x)

Це фактично і є кодування але для поліномів. Поліном g(x) називається породжуючим.

Зараз намагаюсь написати...

1). Перетворення числа у двійковий поліном.
P(x^1)->x+1 -> 11->3
P(x^5)->x^5+x^3+1 ->101001->41
P(x^8)->x^8+x^4+x^3+x^2+1 ->100011101->285
Бачимо, що у скобках стоїть степінь поліному,
а коефіцієнти поліному дорівнюють цифрам двійкового 
розкладу числа.

Кодер. (з *.doc файлу, там інші позначення ніж у Вікіпедії)

Крок 1. Множимо вхідну кодову комбінацію g(x) на одночлен x^m, де m - степінь твірного (породжуючого) 
полінома p(x).

Крок 2. Ділимо g(x)*x^m на твірний поліном p(x).

g(x)*x^m
-------- = q(x) + r(x) / p(x)
p(x)

power(g(x)) = power(q(x)) (степінь)
power(r(x)) < m
q(x) - частка від ділення.
r(x) - залишок від ділення.

Тобто для закодованого повідомлення, враховуючи особливості алгебри двійкового поля, отримаємо для результуючого полінома

f(x) = p(x) * q(x) = g(x) * x^m + r(x).

Де f(x) - закодований поліном.

Програма

void main()
{
	int i;

	int data;
	int code;
	int m_data[100], p_data;
	int m_code[100], p_code;
	int r,d;

	data = 13; // 8 + 4 + 0 + 1

	d = data;
	p_data = 0;
	while(d>0)
	{
		r = d % 2; d = d / 2;
		m_data[p_data] = r;
		p_data ++;
	};

	code = 11; // 8 + 0 + 2 + 1

	d = code;
	p_code = 0;
	while(d>0)
	{
		r = d % 2; d = d / 2;
		m_code[p_code] = r;
		p_code ++;
	};

	int m = p_code - 1; // Визначення степені полінома з кодом

	// Шукаємо g(x) * x ^ m
	int gxxm[100];
	int gxxm_[100];
	int pgxxm = p_data + m;
	int p_data_;

	for(i=0; i< =pgxxm - 1; i++)
	{
		gxxm[ i] = 0;
		gxxm_[ i]=0;
	};

	p_data_ = p_data;
	while(p_data>-1)
	{
		gxxm[p_data + m] = m_data[p_data];
		gxxm_[p_data + m] = m_data[p_data];
		p_data--;		
	};
	p_data = p_data_;

	// Обрахунок r(x)
	int rx[100];
	int p_rx;

        //...

	
	// Обрахунок gxxm = gxxm_ + rx

        //...

}

Тут ніяких бібліотек

Поки ніяких бібліотек не потрібно. Просто повставляв пробіли в [i ] та = >. (Прогляньте синтаксис gxxm[ i] = 0; gxxm_[ i]=0; i< =pgxxm ) Їх цей редактор як теги читає. Це був тільки фрагмент. З чисел отримується їх двійковий розклад (коефіцієнти поліномів).

Усе втомився ...

// Якась програма є ...
// Треба доробити останню дію (мабуть проксорити масив по r[]),
// тоді буде кодер, на декодер мене не вистачить бо треба писати диплом.
// Я вишлю код на EMAIL, скоріш за все там правильно, мінімум
// він компілюється, але треба протрасувати його.

int i;
int r,d;
int m;

int data;
int code;
int m_data[100], p_data, p_data_;
int m_code[100], p_code;

int gxxm[100], p_gxxm;
int gxxm_[100], p_gxxm_;
int rx[100], p_rx;
int minus[100], p_minus;

// m_code[] < gxxm_[]
bool b1()
{
	if(p_code > p_gxxm_)
	{
		return false;
	} else
	{
		if(p_code < p_gxxm_)
		{
			return true;
		} else
		{
			i = p_code;
			while((gxxm_[ i ]==m_code[ i ])&&(i>0))
			{
				i--;
			};
			if(gxxm_[ i ]>m_code[ i ])
			{
				return true;
			} else
			{
				return false;
			};
		};
	};	
}

// minus[] < gxxm_[]
bool b2()
{
	if(p_minus > p_gxxm_)
	{
		return false;
	} else
	{
		if(p_minus < p_gxxm_)
		{
			return true;
		} else
		{
			i = p_minus;
			while((minus[ i ]==gxxm_[ i ])&&(i >0))
			{
				i--;
			};
			if(gxxm_[ i ] > minus[ i ])
			{
				return true;
			} else
			{
				return false;
			};
		};
	};	
}

void main()
{
	data = 13; // 8 + 4 + 0 + 1

	d = data;
	p_data = 0;
	while(d>0)
	{
		r = d % 2; d = d / 2;
		m_data[p_data] = r;
		p_data ++;
	};

	code = 11; // 8 + 0 + 2 + 1

	d = code;
	p_code = 0;
	while(d>0)
	{
		r = d % 2; d = d / 2;
		m_code[p_code] = r;
		p_code ++;
	};

	m = p_code - 1; // Визначення степені полінома з кодом

	// Шукаємо g(x) * x ^ m
	p_gxxm = p_data + m;
	p_gxxm_ = p_gxxm;

	for(i=0; i< =p_gxxm - 1; i++)
	{
		gxxm[ i ] = 0;
		gxxm_[ i ]=0;
	};

	p_data_ = p_data;
	while(p_data>-1)
	{
		gxxm[p_data + m] = m_data[p_data];
		gxxm_[p_data + m] = m_data[p_data];
		p_data--;		
	};
	p_data = p_data_;

	// Обрахунок r(x)

	while(b1() == true)
	{
		for(i = 0; i< =p_code - 1; i++)
		{
			minus[ i ] = m_code[ i ];
		};
		p_minus = p_code;
		while (b2() == true)
		{
			for(i = p_minus; i>-1; i--)
			{
				minus[i+1] = minus[ i ];
			};
			minus[0] = 0;
			p_minus++;
		};
		for(i = 0; i< =p_minus - 1; i++)
		{
			gxxm_[ i ] = gxxm_[ i ] - minus[ i ];
		};
		
		// Корекція числа gxxm_[];
		i=0;
		while(i< =p_gxxm_)
		{
			while(gxxm_[ i ] < 0)
			{
				gxxm_[ i+1]--; // Займаємо одиничку з старшого розряду
				gxxm_[ i] = gxxm_[ i] + 2;				
			};
			i++;
		};
		if(gxxm_[p_gxxm_] >0)
		{
			p_gxxm_ = p_gxxm_;
		} else
		{
			p_gxxm_--; // При діленні вже використан старший розряд
		};
	};

	for(i = 0; i< =p_gxxm_; i++)
	{
		rx[ i] = gxxm_[ i];
	};
	p_rx = p_gxxm_;


	// Треба реалізувати обрахунок gxxm = gxxm_ + rx

}