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

[Mister_DSP]

Добрый день.

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

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

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

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

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

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

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

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

[MrYuran]

Зависит от характера ошибок. Например, сверточные коды эффективно исправляют битые пачки, блочные - единичные ошибки.
Для повышения эффективности применяют каскадное кодирование, например, Рида-Соломона поверх БЧХ.
Но естественно, за это придется заплатить. (в смысле, дополнительными контрольными блоками)

[Mister_DSP]

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

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

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

[litv]

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

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

[Mister_DSP]

Для кода Хэмминга : эффективность кода растет при увеличении информационных блоков. Так, для кодирования 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, оно эффективнее Голея и Хемминга будет

[_4afc_]

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

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

Допустим ваш код (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мС

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

[andyp]

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

Для BSC - граница Хамминга (https://en.wikipedia.org/wiki/Hamming_bound).

[Mister_DSP]

_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 фреймов потеряны.

[Maverick]

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

Код 8B/10B
Используется та же схема для кодирования, т.е. 8 бит кодируются 10-битным символом. Здесь 4-кратная избыточность (28=256; 210=1024), т.к. 256 возможных входных значений кодируются 1024 выходными.
Этот код обеспечивает стабильное соотношение 0 и 1 в выходном потоке, не зависящем от входных данных. Это свойство актуально для лазерных оптических передатчиков. От данного соотношения зависит их нагрев и при колебании степени нагрева увеличивается количество ошибок приема. Применяется в гигабитной сети на оптоволокне.

[Mister_DSP]

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

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

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

Сообщение отредактировал Mister_DSP - Jan 20 2017, 13:15

[petrov]

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

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

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

[MrYuran]

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

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

[Maverick]

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

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

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

[Mister_DSP]

Создатель 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 ( 255.67 килобайт ) Кол-во скачиваний: 47


Код:

Код

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 - Jan 20 2017, 15:28

[Dr.Alex]

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

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

Существуют ли другие алгоритмы коррекции битовых ошибок в коротких пакетах, которые исправляют 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 ошибку?

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