Перейти к содержанию
    

Корректирующие коды (эффективнее чем Голей, Хемминг)

Добрый день.

 

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

 

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

 

В приёмнике и передатчике требуется организовать эффективную битовую коррекцию ошибок.

 

Читал про коды Хемминга и Голея: код Хемминга (7,4) исправляет 1 ошибку - эффективность: 1/7

Код Голея (24,12) исправляет 3 ошибки - эффективность 3/24 = 1/8

 

Существуют ли другие алгоритмы коррекции битовых ошибок в коротких пакетах, которые исправляют 1/4 - 1/2 числа бит от общего потока?

 

К примеру, из общего кодового слова длиной 24 бита исправить 6... 12 бит?

 

Каков предел эффективности?

 

Блочные коды (работающие с блоками бит типа RS- и Turbo- code) не предлагать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Зависит от характера ошибок. Например, сверточные коды эффективно исправляют битые пачки, блочные - единичные ошибки.

Для повышения эффективности применяют каскадное кодирование, например, Рида-Соломона поверх БЧХ.

Но естественно, за это придется заплатить. (в смысле, дополнительными контрольными блоками)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

От такого рода нестабильностей, программно что можно предпринять (чутьё и антенны выжаты на максимум). Связь между двумя идущими по улице людьми.

 

Исходный пакет очень короткий - 3-4 байта, допустимо навернуть до 2 раза больше, тоесть код-рейт 0,5 не ниже.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Для кода Хэмминга : эффективность кода растет при увеличении информационных блоков. Так, для кодирования 7 бит данных избыточность составляет чуть больше 57%, для кодирования 256 бит избыточность будет 3.5%, а для 1024 – 1%.

 

http://all-ht.ru/inf/systems/p_0_14.html

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Для кода Хэмминга : эффективность кода растет при увеличении информационных блоков. Так, для кодирования 7 бит данных избыточность составляет чуть больше 57%, для кодирования 256 бит избыточность будет 3.5%, а для 1024 – 1%.

 

http://all-ht.ru/inf/systems/p_0_14.html

 

Вы представляете что такое 256 бит на скорости 700 бит/с (вокодер)? :)

Это 0,73 секунды задержки звука в симплексном канале (половина времени - задержка на передачу и столько же на приём).

 

Нужен алгоритм именно для коротких пакетов.

 

Пока рассматриваю вот это : http://www.iz-news.ru/lect/04/

 

И это (клондайк программиста-цифровика :) ) : http://the-art-of-ecc.com/topics.html

 

Ну и тут http://the-art-of-ecc.com/3_Cyclic_BCH/RBDS.c в исходнике реализация кодера/декодера (26,12) с исправлением до 5 ошибок, эффективность 5/26 = 0,192 - почти 1/5, оно эффективнее Голея и Хемминга будет :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

Если искажается весь пакет - надо размазать данные по другим пакетам, а не исправлять ошибки в искаженном

 

Допустим ваш код (7,4,3) исправляет 1 ошибку

 

При байтовом доступе к данным:

 

Берём 14 исходных байт (28*4)

кодируем -> (28*7)

перемежаем -> (7*28)

отправляем 7 пакетов по 32 бита (4 можно использовать для синхронизации)

декодируем в обратном порядке

 

Вывод:

любой из семи пакетов может быть полностью искажен

наворот (7*32)/(28*4)=2

при 700 бит/с в эфире:

невоспреимчивость к помехе длиной 32/700 = 46мС

задержка в приёмнике 7*32/700=320мС

 

Можно кодировать полубайтами по 7 байт, а отправлять также по 32 бита по 2 группы в пакете (4+14+14)

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

 

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

_4afc_, большое Вам спасибо!

 

Благодаря Вашему примеру, я начал кое-что понимать... а именно: корректировать не испорченный пакет, а работать с группой перемежённых пакетов.

 

В случае с вокодером Codec2 на 700 бит/с, составил свой пример:

 

Берём 8 фреймов вокодера по 28 бит каждый - это 56 x 4 бит

Далее кодируем с избыточностью (56 x 4) => (56 x 7)

Перемежаем: (56 x 7) => (7 x 56)

Отправляем 7 пакетов по 56 бит (по 7 байт).

 

Декодирование в обратном порядке.

Из 7 пакетов один любой может быть полностью испорчен(не подлежать восстановлению?)

 

При 700 бит/с невосприимчивость к помехе: 56/700 = 80 мс - это два речевых фрейма Codec2 !

 

Итого 8 фреймов из них допускается 2 битых.

 

Всё ли верно?

 

Есть ли более эффективные коды, чем (7,4) - либо бОльшее число ошибок при заданной длине или более короткая длина на 1 ошибку?

 

 

А если приемник не примет пакет? Будет нарушение синхронизации, в итоге все 8 фреймов потеряны.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

может еще посмотреть например на кодирование 8b/10b или подобное?

 

Код 8B/10B

Используется та же схема для кодирования, т.е. 8 бит кодируются 10-битным символом. Здесь 4-кратная избыточность (28=256; 210=1024), т.к. 256 возможных входных значений кодируются 1024 выходными.

Этот код обеспечивает стабильное соотношение 0 и 1 в выходном потоке, не зависящем от входных данных. Это свойство актуально для лазерных оптических передатчиков. От данного соотношения зависит их нагрев и при колебании степени нагрева увеличивается количество ошибок приема. Применяется в гигабитной сети на оптоволокне.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

может еще посмотреть например на кодирование 8b/10b или подобное?

спасибо, почитаю.

 

На счет пакетов, ведь можно не отправлять в моём случае 7 пакетов по 56 бит - можно сгруппировать в один длинный пакет, один фиг - коррекция ошибок будет просто идти на несколько блоков. Зато это исключает синхронизацию.(точнее - дает право её не делать)

Изменено пользователем Mister_DSP

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

спасибо, почитаю.

 

На счет пакетов, ведь можно не отправлять в моём случае 7 пакетов по 56 бит - можно сгруппировать в один длинный пакет, один фиг - коррекция ошибок будет просто идти на несколько блоков. Зато это исключает синхронизацию.(точнее - дает право её не делать)

 

Берите максимально длинный бинарный БЧХ, который устроит по задержке и слышимым искажениям от потери всего пакета, их полно, есть из чего выбрать. В перемежении нет толка в смысле усиления в АБГШ канале.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

может еще посмотреть например на кодирование 8b/10b или подобное?

Это совсем другое, для устранения длинных последовательностей нулей и единиц и улучшения синхронизации. Что-то сродни манчестеру, в некотором смысле.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Это совсем другое, для устранения длинных последовательностей нулей и единиц и улучшения синхронизации. Что-то сродни манчестеру, в некотором смысле.

я это понимаю....

но иногда ошибки могут возникть именно из-за рассинхронизации приемника и передатчика...

 

Про физику канала ТС ничего не написал...

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Создатель Codec2 Дэвид в своем сайте пишет, что планирует добавить FEC к своему детищу - защитив только важные биты фрейма:

http://www.rowetel.com/?p=5373 читать со слов "Next Steps Some thoughts on FEC. A (23,12) Golay code........"

 

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

В общем: важны только 13 бит из 28 - биты кодовой книги, старшие биты тона и усиления.

Остальные не дают теряться разборчивости речи: попробовал занулить их - в итоге речь как была так и осталась.

 

Так что... (13/28)*700 = 325 бит/с - до такого можно снизить битрейт.

 

Ну а идею защиты только важных бит можно принять на вооружение.

 

Cделал запись с занулёнными незначимыми битами, оставив 13 из 28.

 

Звучит ИМХО не дурно, что дает 325 бит/с

325bit_from_700C.wav

 

Код:

codec2=codec2_create(CODEC2_MODE_700C);

while(fread(buf,sizeof(short),320,f_in)==320)
{
  codec2_encode(codec2,bits,buf);

//bits[3]^=0x08; //01234567 (!не влияют89_10_11_12_13_14) 15_16(pitch)_17(pitch) (не влияет: 18_19) 20(усиление)_21 (не влияет: 22_23_24_25_26_27)

bits[1]&=0x80; //зануляем биты 8...14
bits[2]&=0x33; //зануляем биты 18..19, 22..23

  fwrite(bits,sizeof(char),4,f_out);
}

codec2_destroy(codec2);

 

Берите максимально длинный бинарный БЧХ, который устроит по задержке и слышимым искажениям от потери всего пакета, их полно, есть из чего выбрать. В перемежении нет толка в смысле усиления в АБГШ канале

Выпадают пакеты при передвижении в граничных условиях когда расстояние на пределе. БЧХ поможет в этом случае? Каков выигрыш в отношении сигнал/шум ожидать - на сколько снизится?

Изменено пользователем Mister_DSP

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Блочные коды не предлагать.

Ваши Хэмминг и Голей тоже систематические линейные блоковые коды.

 

 

Существуют ли другие алгоритмы коррекции битовых ошибок в коротких пакетах, которые исправляют 1/4 - 1/2 числа бит от общего потока?

К примеру, из общего кодового слова длиной 24 бита исправить 6... 12 бит?

Каков предел эффективности?

 

:-)))))))))) Между 1/4 и 1/2 мягко говоря очень большая разница, примерно как между 1-ой космической скоростью и скоростью света :-)))))))

Можно бесконечно приближаться к 1/2, но при этом избыточность будет приближаться к 100% (из миллиона бит только 1 будет информационным, остальные проверочные).

(Не забываем, что вы просили 1/2 от ВСЕГО БЛОКА, а какова там полезная доля не сказали.)

Исправить 1/4 от всего блока уже вполне реально, но код будет длинный (десятки тысяч бит), а скорость кода будет ну где-то 1/4.

 

НАПОМИНАЮ:

Хорошие коды подразумевают мягенькое декодирование,

поэтому там вообще-то нет понятия "ошибки".

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

 

 

я начал кое-что понимать... а именно: корректировать не испорченный пакет, а работать с группой перемежённых пакетов.

Всё ли верно?

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

Чтобы толк был (если вы вообще согласны задержку увеличить), нужно сделать пакет максимальной длины (исходя из приемлемой задержки),

как уже и сказал Петров.

 

 

Есть ли более эффективные коды, чем (7,4) - либо бОльшее число ошибок при заданной длине или более короткая длина на 1 ошибку?

Нет, науке не известно.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...