2D Reed-Solomon Block Turbo Codes (RS BTC)

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

Под реализацией понимается — реализация для микроконтроллеров. А не для DSP, PC, FPGA и прочих кодировщиков.



Когда стандартные методы, такие как FEC и Каскад, не работают или работаю плохо. Корреляционный прием не спасает. То остается только одно. Использовать турбокод.

Речь пойдет о блочном турбокоде. Который по хорошему нужно реализовывать на FPGA ибо матрицы очень хорошо распараллеливаются. Хотя и высокопроизводительного ARM будет достаточно. А для кодировки так и AVR можно использовать.

Принцип действия можно описать одной картинкой

wireless-e.ru/articles/technologies/2006_1_63.php
Статейку для понимания конечно-же нужно прочесть. Там расписано как это работает.

Приступаем


unsigned char msg[MSG_LEN*MSG_LEN]={0};

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

ВАЖНО: Если используется не весь буфер, то оставшиеся байты должны быть заполнены терминатором.

Т.к. в моем случае передаются бинарные данные, то используется упрощенная версия Кода Рида-Соломона без erasures. Если передаются ASCI коды, то желательно использовать полную версию.

В файле reedsolomon.h определяем размер RS кодов(переменная MAX_E).

unsigned char codeword[(MSG_LEN+NPAR)*(MSG_LEN+NPAR)]={0};

Выделяем место под закодированное сообщение.

Кодируем:
btc_2d_code(msg,codeword,MSG_LEN);


где:
msg — исходное сообщение;
codeword — закодированное сообщение;
MSG_LEN — длина строки исходного сообщения.

Внутри
//encode 2D
	for(i=0;i<len;i++)
	{
		/* Encode data into codeword, adding NPAR parity bytes */
		encode_data((msg+len*i), len, (codeword+(len+NPAR)*i));
	}
	
	transpose(codeword,len+NPAR);

	for(i=0;i<(len+NPAR);i++)
	{
		/* Encode data into codeword, adding NPAR parity bytes */
		encode_data((codeword+(len+NPAR)*i), len,(codeword+(len+NPAR)*i));
	}


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

Принимаем
if(btc_2d_decode(codeword,msg,MSG_LEN,1)==TRUE)

Функция вернет TRUE в случае успеха.

где
codeword — закодированное сообщение.
msg — буфер для исходного.
MSG_LEN — длина строки исходного сообщения.
1 — количество дополнительных итераций.

ВАЖНО: Перед декодированием сообщения обязательно проверить CRC(на картинке видно где хранятся данные). Возможно данные не повреждены и ничего восстанавливать не нужно. Это один из винов RS BTC. Если повреждены, то обязательно восстановить терминаторы.

Внутри
for(i=0;i<row_count;i++)
{
	/* Now decode -- encoded codeword size must be passed */
	decode_data((codeword+(len+NPAR)*i), len+NPAR);

	/* check if syndrome is all zeros */
	if (check_syndrome () != 0) 
	{
		if(correct_errors_erasures ((codeword+(len+NPAR)*i), len+NPAR)==FALSE)
		{
			err++;
		}
	 }
}//for


Сначала идет проход по строкам.

if(err==0)
{
	//if necessary, then matrix transpose
	if(invert==TRUE)
	{
		transpose(codeword,len+NPAR);
	}
	break;
}


Если все ошибки исправлены, то процедура завершиться.

Иначе
//matrix transpose
transpose(codeword,len+NPAR);

if(invert==TRUE)
{
	invert=FALSE;

	if(err<colm_err)
	{
		colm_err=err;
	}
	else
	{
		if(additional_iteration>0)
		{
			additional_iteration--;
			colm_err=0xFF;
		}
		else
		{
			break;
		}					
	}

	row_count=len;
}
else
{
	invert=TRUE;

	if(err<row_err)
	{
		row_err=err;
	}
	else
	{
		if(additional_iteration>0)
		{
			additional_iteration--;
			row_err=0xFF;	
		}
		else
		{
			break;
		}
	}

	row_count=len+NPAR;				
}


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

В конце
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//In this place you can insert the CRC check
//If CRC correct, then err=0
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

if(err>0)
{
	return FALSE;
}
else
{
	//cut the original message
	for(i=0;i<len;i++)
	{
		for(j=0;j<len;j++)
		{
			*(msg+len*i+j)=*(codeword+(len+NPAR)*i+j);
		}
	}
        return TRUE;
}


Сначала делаем проверку CRC. Даже если декодирование завершилось неудачей. Есть вероятность, что повреждены только RS коды. Если проверка прошла успешно, то сбрасываем err в ноль.

Заключение


Код Рида-Соломона можно заменить на Хеминга или БЧХ. Тогда помехоустойчивость будет выше, но снизится пропускная способность.
Код в архиве. Либу обязательно следует оптимизировать под конкретную задачу.
  • 0
  • 27 января 2013, 23:51
  • a9d
  • 1
Файлы в топике: BTC.zip

Комментарии (0)

RSS свернуть / развернуть
Автор топика запретил добавлять комментарии