Каскадное кодирование Рида — Соломона\Витерби.

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

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


Каскад Рида — Соломона\Витерби — это связка двух алгоритмов которые исправляют ошибки в пакете данных переданному по каналу с шумом. Это утверждение не совсем «корректно» и сильно упрощенно.

Зачем такое вообще используют?

Витерби — отлично справляется с одиночными ошибками. Например если повредить по биту в каждом байте посылки (Витерби способен на большее и «еще» большее после Перемежителя), то посылка будет востановленна. А вот если повредить некоторые байты «полностью», то уже ничего хорошего не выйдет.

Код Рида-Соломона — отлично справляется с пакетными ошибками. Он умеет восстанавливать байты, но он не справится с задачей когда все байты имеют одиночную ошибку.

Объединив эти алгоритмы можно получить достоинства обоих способов кодирования.

Да, это не турбокоды, но очень близко. Да и турбокод не запихать в микроконтроллер. К статье прикреплен архив с примером старого алгоритма одного из турбокодов. Самые прогрессивные алгоритмы турбокодов доступны только за деньги или нужно очень хорошо шарить в теме.

Задача



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

Ориентироваться следует сразу на ARM. Но если требуется только передача, то можно использовать и что-то послабее.
Кодировать сообщение намного легче, чем декодировать.

Настройки трансивера



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

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

Приступаем


Код Витерсби я взял в апнотах от Ti «Design Note DN507» и «Design Note DN504». Рида-Соломона у Henry Minsky. Все это объединил и допилил.

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

Кодирование происходит по схеме:
Рида-Соломона -> Перемежитель -> Витерби -> Перемежитель

Декодирование:
Перемежитель -> Витерби -> Перемежитель -> Рида-Соломона

Код Рида-Соломона


Открываем файл reedsolomon.h. В нем нужно определить две переменный которые определят размер служебных данных.

MAX_E — количество ошибок позиций которых мы не знаем. Т.е. не знаем какие байты повреждены.
MAX_K — количество ошибок позиции которых мы знаем. Т.е. знаем какие байты повреждены.

С MAX_E все понятно а вот с MAX_K уже труднее. Дело в том, что почти всегда есть определенные байты значение которых известно наперед.
Например:
  • первый байт часто определяет размер полезных данных. Его возможные значения могут быть известны наперед.(размер посылки и размер полезных данных разные значения)
  • могут быть байты которые определяют тип пакета, команды и т.д. Их положения и возможные значения известны наперед.
  • пакет может содержать asci коды. Все допустимые значения известны наперед и их легко проверить.


Вот это и определяет MAX_K. Если используется три поля: размер, тип, команда. И можно проверить их правильность. То тогда выбираем MAX_K = 3. Больше ставить бессмысленно.

//2E + K
//E errors, and K erasures

#define MAX_E 3
#define MAX_K 2

//#define NPAR 5
#define NPAR (2*MAX_E+MAX_K)


Соответственно размер служебных данных составил 8 байт. Также в этой конкретной реализации «длина сообщения»(включая CRC)+NPAR должна быть кратна четырем. Это связанно с использованным перемежителем.

Перемежитель


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

Например никто не мешает забрать перемежитель спираль из турбокода.

Использование


unsigned char msg[] = "Nervously I loaded the twin ducks aboard the revolving platform....";

В демо используется сообщение длинной 68 байт + NPAR = 76.

Размер буферов для кодированного сообщения определяют по формуле
fecLen = 4*(((len+TERMINATOR+NPAR)/2)+1);

TERMINATOR = 2

Кодирование
encode(msg,len,inter,codeword,fecLen);


msg — сообщение + CRC.
len — длинна пакета + CRC.
inter — буфер для перемяжителя. Размер равен codeword.
codeword — закодированное сообщение.
fecLen — размер закодированного сообщения.


        //add simple error
	for (i = 0; i < fecLen; i+=3)
	{
		codeword[i]^=0x81;
	}

	//add hard errror
	codeword[24]=0xFF;


Этот пример демонстрирует случай когда Витерби не справляется и дело завершает код Рида-Соломона.
В реальной жизни помеха так не распространяется.

if(decode(codeword,inter,fecLen,msg,len)==TRUE)
	{
		printf("Input: [%5d bytes]\n", len);
		printf("Msg data is: \"%s\"\n", msg);
		printf("\n\n");
	}
	else
	{
		printf("Fail");
		printf("\n\n");
	}


Внутри

        UINT8 i;
	UINT8 erasures[MAX_K];
	UINT8 nerasures = 0;

	// Perform interleaving 
	interleaved(codeword,interl,nFecBytes);

	//FEC decode
	fecDecode(interl,codeword,nbytes+TERMINATOR+NPAR);

	//Perform interleaving
	interleaved(codeword,interl,nbytes+NPAR);

	//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	//In this place you can insert the CRC check
	//If the CRC is correct, then copy interl in msg and finish the function with code TRUE
	//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	//RS decode
	/* Now decode -- encoded codeword size must be passed */
    decode_data(interl, nbytes+NPAR);

	/* check if syndrome is all zeros */
	if (check_syndrome () != 0) {

		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		// In this place paste your code to search erasures
		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!		
		//if(interl[1]!='e')
		//{
		//	erasures[nerasures++] = nbytes+NPAR-2;   //starting from 1
		//}

		if(correct_errors_erasures (interl,nbytes+NPAR,nerasures,erasures)==FALSE)
		{
			return FALSE;
		}
		else
		{
			//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
			//In this place you can insert the CRC check
			//If CRC incorect, then return FALSE
			//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		}
	 }

	//copy inter to msg
	for(i=0;i<nbytes;i++)
	{
		msg[i]=interl[i];
	}

	return TRUE;


Вместо

        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	//In this place you can insert the CRC check
	//If the CRC is correct, then copy interl in msg and finish the function with code TRUE
	//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


Вставляем проверку CRC. Если совпало то копируем сообщение в msg и завершаем функцию с кодом TRUE.


                //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		// In this place paste your code to search erasures
		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!		
		//if(interl[1]!='e')
		//{
		//	erasures[nerasures++] = nbytes+NPAR-2;   //starting from 1
		//}


Здесь вставляем проверку служебных полей сообщения. Если, что-то не корректно, то делаем пометки в erasures. Индексация начинается с 1. Т.е. если байт с индексом 0 поврежден, то отнимать нужно 1.

Естественно проверок должно быть столько сколько определено в MAX_K.


                        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
			//In this place you can insert the CRC check
			//If CRC incorect, then return FALSE
			//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


Вставляем проверку CRC. Если не совпало, то завершаем функцию с кодом FALSE.

Вот и все. Адаптируем код под свой проект и вперед. Для либы требуется ~1-2 КБ оперативки, зависит от параметров и вашей оптимизации.
  • +1
  • 26 января 2013, 00:12
  • a9d
  • 2
Файлы в топике: TurboCode.zip, Viterbi_RS.zip

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

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