[_Leo_ 0]

Необходимо написать программу восстанавливающую данные - файл JPEG, переданные по беспроводному каналу.

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

 

должна превышать 10% от изначального объёма.

Если чуть подробнее, то полученная картинка обрабатывается (кодируется) микроконтроллером AVR32 AT32UC3 и передаётся по

 

беспроводному каналу NanoNet. Принимаются данные на ПК, там происходит их декодирование. Язык программирования С.

 

Так как повторная передача исключена, то кроме корректирующих кодов вариантов вроде нет.

Корректирующие коды выбираются исходя из наиболее вероятного типа ошибок, вот тут пробел - какой тип ошибок более характерен для

 

NanoNet? У него частота что и у WiFi, но модуляция другая.

Для одиночных ошибок лучше всего подходит классика - код Хемминга. Учитывая 10% ограничение минимально возможный код (63, 57).

Только работа в с файлами происходит побайтно и использование такого кода означает лишние сдвиги, создание массивов и т.д. Как вариант

 

код (88,80), но он избыточен и лишь чуть более удобен.

Циклические коды БЧХ или Рида-Соломона выглядят более привлекательными и вроде не сложны в реализации. У БЧХ как я понимаю можно

 

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

 

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

С благодарностью приму любой совет.

[r_dot 0]

повторная передача исключена

Это зря вы так.

Потеря одного бита при передаче по эфиру - практически нереальная ситуация.

Если на радиоканал действует помеха (например, при искре от мощного контактора), то вышибает сразу блок данных, а то и синхронизацию.

Без повтора всякая коррекция - мёртвому припарки. Естественно, это сугубо моё личное мнение, основанное на сугубо собственном опыте.

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

С датчиков, например, сигнал всегда циклически повторяется гораздо чаще, чем изменяется измеряемая величина.

 

Если нужна действительно достоверная передача, без обратного канала с подтверждением приёма задача решается только вероятностно, то есть при однократной передаче с требованием 100% достоверности приёма - никак не решается.

[juvf 17]

Если нужна действительно достоверная передача, без обратного канала с подтверждением приёма задача решается только вероятностно, то есть при однократной передаче с требованием 100% достоверности приёма - никак не решается.

 

+1

[mdmitry 0]

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

[vallav 0]

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

 

Так вроде если есть возможность видеоданные поджать ( хотя бы на 20% ) появится в реальном времени и место для контрольных данных и время для

повторной выдачи сбойных пакетов.

[V_G 11]

Так вроде если есть возможность видеоданные поджать ( хотя бы на 20% ) появится в реальном времени и место для контрольных данных и время для повторной выдачи сбойных пакетов.

По-любому надо вводить избыточность (перезапросы или коды, исправляющие ошибки). Но если неисправимый сбой случится с jpeg картинкой, она будет испрочена достаточно сильно. А если не сжимать, выпадет несколько пикселов, которые и не заметишь. Так что может, не стоит сжимать картинку, а гнать bmp? Дальше человеческий глаз - лучший из фильтров!

Изменено 30 апреля, 2010 пользователем V_G

[vallav 0]

По-любому надо вводить избыточность (перезапросы или коды, исправляющие ошибки). Но если неисправимый сбой случится с jpeg картинкой, она будет испрочена достаточно сильно. А если не сжимать, выпадет несколько пикселов, которые и не заметишь. Так что может, не стоит сжимать картинку, а гнать bmp? Дальше человеческий глаз - лучший из фильтров!

 

Ре понял.

Вы полагаете, что, если будет сбой в передаче, который не получится восстановить повторной передачей ( вылетит больше 10% пакетов ),

то такой сбой будет незаметен на глаз при передаче некодированного видео?

И - лучше постоянные точечные помехи на картинке, чем чистая картинка, иногда сильно искажающаяся?

Вопрос был - как передать видео без искажений.

Согласен, мое предложение не проходит, если искажается более 10% пакетов.

[V_G 11]

то такой сбой будет незаметен на глаз при передаче некодированного видео?

И - лучше постоянные точечные помехи на картинке, чем чистая картинка, иногда сильно искажающаяся?

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

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

Я к тому, что в IP-телефонии используется (вроде как) UDP-протокол, или что-то похожее, без повторных запросов. Заранее мирятся с некоей потерей информации. Может, и тут так можно поступить?

Изменено 30 апреля, 2010 пользователем V_G

[_Leo_ 0]

Приятно видеть живое обсуждение темы.

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

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

 

 

Изображение черно-белое, поступает с камеры 640х480, образца изображения к сожалению нет.

BER увы не известен в даном случае.

А вообще технология NanoNet довольно стойкая к помехам: модуляция NanoNet помехоустойчиваяt, там есть аппаратная реализация

Хемминга (7, 4), причём с перемешиванием, таким образом достигается исправление 2 ошибок на байт, есть и CRC32 (для интересующихся:

 

wireless-e ru, там есть статьи по данной технологии).

Но вот только при включении аппаратной коррекции информационная скорость падает в соответственно в 2 раза, что неприемлимо.

 

Тестовый образец изображения приходится создавать самому, конвертировал черно-белый .BMP в трех программах: Paint, ACD See и PhotoShop,

 

в JPEG.

В двух первых в файле один сегмент, а вот фотошоп напихал туда чего то своего и в файле три сегмента. Ну да это ладно.

 

Заголовочная информация (определяю так для себя, то что до 0xFFDA) занимает приблизительно 2% от объема файла. С учетом заданного

 

ограничения избыточности в 10% от объема файла, добавачная информация при кодировании заголовка может превышать объём самого

 

заголовка в 5 раз, есть простор для фантазии)).

Кодировать весь заголовок я хочу потому что там содержится служебная информация о процессе кодирования-декодирования, таблица

 

квантования как я понимаю тоже одна и её порча влияет на отображения каждого блока 8х8. Ну и таблица Хаффмана конечно.

А единичные ошибки в данных, как понимаю влияют на блок 8х8.

 

Задача, поставленная на данный момент - реализация простого (и менее ресурсоёмкого) алгоритма устраняющего одиночные ошибки, раз BER

 

не известен, тогда защищаем минимально возможный объём информации - байт или даже полбайта.

В соответствующей литературе

(

опять для тех кому будет интересно:

Блейхут Р. Теория и практика кодов, контролирующих ошибки 1986

Золотарёв В.В. Овечкин Г.В. Помехоустойчивое кодирование. 2004

Кларк Дж. Кейн Дж. Кодирование с исправлением ошибок

Питерсон У. Коды, исправляющие ошибки. 1976

Цифровая связь. Теоретические основы и практическое применение (Бернард Скляр)

это и прочие книги есть например на twirpx com

)

указывают, что достаточно просты и эффективны циклические алгоритмы.

Например для полубайта - циклический код Хемминга (7, 4), чтобы избежать дополнительных сдвигов можно реализовать как (8, 4).

На данный момент примерно такие мысли у меня, но открыт для любой корректирующей))) информации.

 

P.S. С полубайтом все более менее ясно, а вот если надо кодировать ровно байт?

В оптимальных циклических кодах n и k нечетные.

То есть надо спроектироват код (16, 8) или другой (n, k) код, где к<n и оба кратны 8.

В Питерсон У. Коды, исправляющие ошибки. 1976, таблица 8.3, есть подобные коды, называются квазициклическими.

Но вот с теорией и примерами их построения не густо. Допустим как определить d (расстояние Хемминга) у (16, 8) или (24, 16), чтобы в свою

очередь определить количество ошибок ими исправляемых.

[blackfin 30]

... таблица квантования как я понимаю тоже одна и её порча влияет на отображения каждого блока 8х8. Ну и таблица Хаффмана конечно.

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

Если же меняются, лучше передавать одно 8-битное число Q как это делают в MJPEG(RTP).

То же касается и таблиц Хаффмана. Они обычно неизменны для всей последовательности MJPEG.

А единичные ошибки в данных, как понимаю влияют на блок 8х8.

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

Изменено 30 апреля, 2010 пользователем blackfin

[mdmitry 0]

BER увы не известен в даном случае.

А вообще технология NanoNet довольно стойкая к помехам: модуляция NanoNet помехоустойчиваяt, там есть аппаратная реализация

Хемминга (7, 4), причём с перемешиванием, таким образом достигается исправление 2 ошибок на байт, есть и CRC32 (для интересующихся:

Система работает довольно устойчиво до тех пор, пока приемник не блокируется помехой, даже узкополосной. Попробуйте одновременно передачу Nanonet и вблизи Bluetooth передатчик. :laughing:

[x736C 0]

Вопрос был - как передать видео без искажений.

Согласен, мое предложение не проходит, если искажается более 10% пакетов.

Вопрос вроде не о видео. Из личного опыта, для видео (мпег 1,2,4) потеря 2-3% — смотреть практически невозможно. Допустимо считается менее 0,5-1%. Где-то были тесты в сети, кажется, на ixbt.

Речь, конечно, о UDP-пакетах.

 

Это зря вы так.

Потеря одного бита при передаче по эфиру - практически нереальная ситуация.

Если на радиоканал действует помеха (например, при искре от мощного контактора), то вышибает сразу блок данных, а то и синхронизацию.

Без повтора всякая коррекция - мёртвому припарки.

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

 

Кстати о требуемой величине времени передачи (назовем latency) автор темы ничего не сказал.

 

То есть надо спроектироват код (16, 8) или другой (n, k) код, где к<n и оба кратны 8.

...

Допустим как определить d (расстояние Хемминга) у (16, 8) или (24, 16), чтобы в свою

очередь определить количество ошибок ими исправляемых.

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

Изменено 30 апреля, 2010 пользователем x736C

[_Leo_ 0]

Просмотрев несклько черно-белых JPEG файлов пожатых с хорошим качеством выяснил, что заголовок (до маркера FFDA)

находится в пределах 0,8 - 1,5%. Округлил до 2%.

Закодировал заголовок циклическим кодом (7, 4).

 

#include <stdio.h>
#include <stdlib.h>


#define BSIZE 512

short int coder(unsigned char);

int main(int argc, char *argv[])
{

unsigned char bufRead[bSIZE], buf2uc[2], a;
FILE *fdWrite, *fdRead;
short int numByte = 0, buf2si[2], i, ac;
int cnt = 0;

fdRead = fopen("a.dat", "rb");
if (fdRead == NULL)
{ 
 printf ("Oshibka pri otkritii faila Read\n");
 exit(1);
}  
else
 printf ("\nFile Read otkrit\n");

fdWrite = fopen("acode.dat","wb");
if (fdWrite == NULL)
{ 
 printf ("Oshibka pri otkritii faila Write\n");
 exit(1);
}  
else
 printf ("File Write otkrit\n");


do
{
 fread(bufRead, sizeof(unsigned char), BSIZE, fdRead);
 for (i = 0; i < (BSIZE - 1); i++)
 {
   if ((bufRead[i] == 0xff) && (bufRead[i+1] == 0xda))
   {
     numByte = cnt*(BSIZE-1) + i + 2;
     break;
   }
 }  
 if (numByte == 0)
 {
   cnt++;
   fseek(fdRead, -1, SEEK_CUR);
 }
}
while (numByte == 0);

printf("\nKodirovat bait %i\n", numByte);

memcpy(buf2uc, &numByte, sizeof buf2uc);
buf2si[0] = coder(buf2uc[0]);
buf2si[1] = coder(buf2uc[1]);
fwrite(buf2si, sizeof(short int), 2, fdWrite);
fseek(fdRead, 0, SEEK_SET);
for (i = 0; i < numByte; i++)
{
 fread(&a, sizeof(unsigned char), 1, fdRead);
 ac = coder(a);
 fwrite(&ac, sizeof(short int), 1, fdWrite);
}

 fread(&a, sizeof(unsigned char), 1, fdRead);
 while (!feof(fdRead))
 {  
   fwrite(&a, sizeof(unsigned char), 1, fdWrite);   
   fread(&a, sizeof(unsigned char), 1, fdRead);  
 }


 if (fclose (fdRead) == 0)
    printf ("File Read zakrit\n");
 else
    printf ("Oshibka pri zakritii faila Read\n"); 

 if (fclose (fdWrite) == 0)
    printf ("File Write zakrit\n");
 else
    printf ("Oshibka pri zakritii faila Write\n");




getch();	
 return 0;
}

short int coder(unsigned char a)
{
unsigned char aH, aH_Code, aL, aL_Code;
short int i, Code;   

/*
a - байт введённый для кодирования.
aH - полученный остаток от деления старших 4 бит.
aH_Code - значение закодированных 4 старших бит.
aL - полученный остаток от деления младших 4 бит.
aL_Code - значение закодированных 4 младших бит.
Code - 2 байтное число, в младшем байте содержится 7 битное число 
полученное при кодировании младших 4 бит введеного числа.
В старшем байте - значение закодированных старших 4 бит.
*/ 

// складываем с маской для обнуления ненужных бит
// в aH хранится старший полубайт его сдвигаем вправо на два разряда
// чтобы коменсировать первый сдвиг влево в цикле
aH = a & 0xf0;
aH_Code = aH >> 1;
aH = aH >> 2;

// складываем с маской для обнуления ненужных бит
// в aL хранится младший полубайт его сдвигаем влево на два разряда
// (надо на три), третий сдвиг - первый сдвиг влево в цикле
aL = a & 0x0f;
aL_Code = aL << 3;
aL = a << 2;
// aH_Code и aL_Code хранят исходные полубайты
// сдвинутые на три разряда влево относительно первого
// к ним происходит присоединение остатка

for (i = 0; i < 4; i++)
{    
 aH = aH << 1;   
 if (aH & 0x40) 
   aH = aH ^ 0x58;       

 aL = aL << 1; 
 if (aL & 0x40) 
   aL = aL ^ 0x58; 
}

// остаток получается сдвинутым на 3 разряда влево, 
// поэтому надо сдвинуть его вправо
aH = aH >> 3;
aH_Code = aH_Code | aH;

aL = aL >> 3;
aL_Code = aL_Code | aL;

//16 битному числу Code присваеваем в старший байт aH_Code,
//а в младший байт aL_Code

Code = aH_Code;
Code = Code << 8;
Code = Code | aL_Code;

 return Code;
}


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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char *argv[])
{

int i, P_err, indention;
unsigned char masErr[8] = {1,2,4,8,16,32,64,128}, a, err;
FILE  *fdRead;
long fileSize, pos;
unsigned char fileName[100];

printf ("Vvedite imya faila: ");
scanf("%s", fileName);

printf ("Na skolko byte otstupit ot nachala faila: ");
scanf("%i", &indention);

printf ("Vvedite chislo byte na kotorie prixoditsa 1 oshibka: ");
scanf("%i", &P_err);

fdRead = fopen(fileName, "r+b");
if (fdRead == NULL)
{ 
 printf ("Oshibka pri otkritii faila Read\n");
 exit(1);
}  
else
 printf ("\nFile Read otkrit\n");

fseek(fdRead,0,SEEK_END);
fileSize = ftell(fdRead);
printf("\nThe size of file is %ld bytes\n",  fileSize);

srand(time(NULL));

for (i = (indention + P_err - 1); i < fileSize; i = i + P_err)
{
 fseek(fdRead, i - rand()%P_err, SEEK_SET); 

//  pos = ftell(fdRead);
//  printf("Pos SEEK_SET+i %i \n",  pos);

 fread(&a, sizeof(unsigned char), 1, fdRead);

//  pos = ftell(fdRead);
//  printf("Pos SEEK_SET+i %i posle chteniya simvola %x\n", pos, a);


 err = masErr[rand()%8];
 a = a ^ err;
//  printf("simvol %x posle ^ c %x\n", a, err);

 fseek(fdRead, -1, SEEK_CUR);

//  pos = ftell(fdRead);
//  printf("Pos SEEK_SET+i-1 %i \n---------------------\n",  pos); 

 fwrite(&a, sizeof(unsigned char), 1, fdRead);
}

 if (fclose (fdRead) == 0)
    printf ("File Read zakrit\n");
 else
    printf ("Oshibka pri zakritii faila Read\n"); 

getch();	
 return 0;
}



Ну и декодер исправляющий ошибки  в закодированной части файла.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BSIZE 512

unsigned char decoder(short int);

int main(int argc, char *argv[])
{

unsigned char bufRead[bSIZE], buf2uc[2], a;
FILE *fdWrite, *fdRead;
long position;
short int numByte, buf2si[2], i, ac;
int cnt = 0, razn = 0;

fdRead = fopen("acode.dat", "rb");
if (fdRead == NULL)
{ 
 printf ("Oshibka pri otkritii faila Read\n");
 exit(1);
}  
else
 printf ("\nFile Read otkrit\n");

fdWrite = fopen("adecode.dat","wb");
if (fdWrite == NULL)
{ 
 printf ("Oshibka pri otkritii faila Write\n");
 exit(1);
}  
else
 printf ("File Write otkrit\n");



fread(buf2si, sizeof(short int), 2, fdRead);
buf2uc[0] = decoder(buf2si[0]);
buf2uc[1] = decoder(buf2si[1]);
memcpy(&numByte, buf2uc, sizeof buf2uc);

for (i = 0; i < numByte; i++)
{
 fread(&ac, sizeof(short int), 1, fdRead);
 a = decoder(ac);
 fwrite(&a, sizeof(unsigned char), 1, fdWrite);
}

 fread(&a, sizeof(unsigned char), 1, fdRead);
 while (!feof(fdRead))
 {  
   fwrite(&a, sizeof(unsigned char), 1, fdWrite);   
   fread(&a, sizeof(unsigned char), 1, fdRead);  
 }

 if (fclose (fdRead) == 0)
    printf ("File Read zakrit\n");
 else
    printf ("Oshibka pri zakritii faila Read\n"); 

 if (fclose (fdWrite) == 0)
    printf ("File Write zakrit\n");
 else
    printf ("Oshibka pri zakritii faila Write\n");


getch();	
 return 0;
}


unsigned char decoder(short int c)
{

unsigned char cL, cH, cH_Decode, cL_Decode, Decode;
short int i;

/*
с - 2 байтное число введённый для декодирования.
сH - полученный остаток от деления старшего байта.
сH_Decode - значение декодированных 4 старших бит.
сL - полученный остаток от деления младшего байта.
cL_Decode - значение декодированных 4 младших бит.
Deode - 1 байтное декодированное число.
*/

cL_Decode = (unsigned char)c;
c = c >> 8;
cH_Decode = (unsigned char)c;
cH = cH_Decode;
cL = cL_Decode;

for (i = 0; i < 4; i++)
{ 
 if (cH & 0x40) 
   cH = cH ^ 0x58; 
 cH = cH << 1; 

 if (cL & 0x40) 
   cL = cL ^ 0x58; 
 cL = cL << 1;   
}

cH = cH >> 4;
cL = cL >> 4;

switch(cH)
{
 case 1:
   printf ("oshibka v 1 bite\n"); 
   cH_Decode = cH_Decode ^ 1;
   break;

 case 2:
   printf ("oshibka v 2 bite\n"); 
   cH_Decode = cH_Decode ^ 2;    
   break;

 case 4:
   printf ("oshibka v 3 bite\n"); 
   cH_Decode = cH_Decode ^ 4;  
   break;

 case 3:
   printf ("oshibka v 4 bite\n"); 
   cH_Decode = cH_Decode ^ 8;       
   break;

 case 6:
   printf ("oshibka v 5 bite\n"); 
   cH_Decode = cH_Decode ^ 16;       
   break;

 case 7:
   printf ("oshibka v 6 bite\n"); 
   cH_Decode = cH_Decode ^ 32;       
   break;

 case 5:
   printf ("oshibka v 7 bite\n"); 
   cH_Decode = cH_Decode ^ 64;       
   break;

 default:

   break;                            
}


cH_Decode = cH_Decode & 0x78;
Decode = cH_Decode << 1;
cH_Decode = cH_Decode >> 3;

switch(cL)
{
 case 1:
   printf ("oshibka v 1 bite\n"); 
   cL_Decode = cL_Decode ^ 1;
   break;

 case 2:
   printf ("oshibka v 2 bite\n"); 
   cL_Decode = cL_Decode ^ 2;    
   break;

 case 4:
   printf ("oshibka v 3 bite\n"); 
   cL_Decode = cL_Decode ^ 4;  
   break;

 case 3:
   printf ("oshibka v 4 bite\n"); 
   cL_Decode = cL_Decode ^ 8;       
   break;

 case 6:
   printf ("oshibka v 5 bite\n"); 
   cL_Decode = cL_Decode ^ 16;       
   break;

 case 7:
   printf ("oshibka v 6 bite\n"); 
   cL_Decode = cL_Decode ^ 32;       
   break;

 case 5:
   printf ("oshibka v 7 bite\n"); 
   cL_Decode = cL_Decode ^ 64;       
   break;

 default:

   break;                            
}

cL_Decode = cL_Decode >> 3;
cL_Decode = cL_Decode & 0x0f;
Decode = Decode | cL_Decode;

return Decode;         
}

 

 

Код конечно не оптимален, написан для проверки идеи.

 

Как результат:

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

ошибки приходились на заголовок.

При кодировании, внесении ошибок и декодировании, файл стабильно открывается, но даже несколько ошибок в данных

зачастую делают его визуально безнадёжно испорченным.

 

Очевидно данные тоже надо кодировать, причем как можно лучше.

Так как 2% избыточности из допустимых 10% использованно, то максимально допустимый вариант БЧХ (127, 120).

Изменено 31 мая, 2010 пользователем rezident
Оформление цитаты исходника.