реклама на сайте
подробности

 
 
4 страниц V   1 2 3 > »   
Reply to this topicStart new topic
> Корректирующие коды (эффективнее чем Голей, Хемминг), существуют?
Mister_DSP
сообщение Jan 20 2017, 07:22
Сообщение #1


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



Добрый день.

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

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

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

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

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

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

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

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


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Jan 20 2017, 07:38
Сообщение #2


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 566
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



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


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
Mister_DSP
сообщение Jan 20 2017, 08:11
Сообщение #3


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



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

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

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


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
litv
сообщение Jan 20 2017, 08:40
Сообщение #4


Местный
***

Группа: Свой
Сообщений: 369
Регистрация: 6-10-04
Из: Воронеж
Пользователь №: 806



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

http://all-ht.ru/inf/systems/p_0_14.html
Go to the top of the page
 
+Quote Post
Mister_DSP
сообщение Jan 20 2017, 09:01
Сообщение #5


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



Цитата(litv @ Jan 20 2017, 09:40) *
Для кода Хэмминга : эффективность кода растет при увеличении информационных блоков. Так, для кодирования 7 бит данных избыточность составляет чуть больше 57%, для кодирования 256 бит избыточность будет 3.5%, а для 1024 – 1%.

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


Вы представляете что такое 256 бит на скорости 700 бит/с (вокодер)? sm.gif
Это 0,73 секунды задержки звука в симплексном канале (половина времени - задержка на передачу и столько же на приём).

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

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

И это (клондайк программиста-цифровика sm.gif ) : 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, оно эффективнее Голея и Хемминга будет sm.gif


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
_4afc_
сообщение Jan 20 2017, 10:08
Сообщение #6


Профессионал
*****

Группа: Свой
Сообщений: 1 024
Регистрация: 13-10-05
Из: Санкт-Петербург
Пользователь №: 9 565



Цитата(Mister_DSP @ Jan 20 2017, 11:11) *
Канал связи чистый, нужно обеспечить приём пакетов в зоне неуверенного приёма, когда к примеру приёмник зацепил преамбулу, а пакет принял с ошибками - из-за движения абонента: меняется напряженность поля и иногда пакет искажается.


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

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

Вообще, если вы считаете, что у вас канал чистый но уходит - надо кодировать данные с повышением степени восстановления к концу пакета т.е. в зависимости от дальности от преамбулы.
Go to the top of the page
 
+Quote Post
andyp
сообщение Jan 20 2017, 10:26
Сообщение #7


Местный
***

Группа: Участник
Сообщений: 395
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Mister_DSP @ Jan 20 2017, 10:22) *
Каков предел эффективности?


Для BSC - граница Хамминга (https://en.wikipedia.org/wiki/Hamming_bound).
Go to the top of the page
 
+Quote Post
Mister_DSP
сообщение Jan 20 2017, 11:22
Сообщение #8


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



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


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
Maverick
сообщение Jan 20 2017, 13:10
Сообщение #9


я только учусь...
******

Группа: Модераторы
Сообщений: 3 225
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Mister_DSP @ Jan 20 2017, 13:22) *

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

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Mister_DSP
сообщение Jan 20 2017, 13:14
Сообщение #10


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



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

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

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

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


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
petrov
сообщение Jan 20 2017, 13:50
Сообщение #11


Гуру
******

Группа: Свой
Сообщений: 2 006
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(Mister_DSP @ Jan 20 2017, 16:14) *
спасибо, почитаю.

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


Берите максимально длинный бинарный БЧХ, который устроит по задержке и слышимым искажениям от потери всего пакета, их полно, есть из чего выбрать. В перемежении нет толка в смысле усиления в АБГШ канале.
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Jan 20 2017, 14:22
Сообщение #12


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 566
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



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

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


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
Maverick
сообщение Jan 20 2017, 15:12
Сообщение #13


я только учусь...
******

Группа: Модераторы
Сообщений: 3 225
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(MrYuran @ Jan 20 2017, 16:22) *
Это совсем другое, для устранения длинных последовательностей нулей и единиц и улучшения синхронизации. Что-то сродни манчестеру, в некотором смысле.

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

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Mister_DSP
сообщение Jan 20 2017, 15:25
Сообщение #14


Частый гость
**

Группа: Участник
Сообщений: 133
Регистрация: 5-11-16
Пользователь №: 94 050



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


Код:
Код
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


--------------------
SPY vs. SPY
Хорошо там, где нет ничего...
Go to the top of the page
 
+Quote Post
Dr.Alex
сообщение Jan 20 2017, 15:34
Сообщение #15


Профессионал
*****

Группа: Свой
Сообщений: 1 196
Регистрация: 5-04-05
Из: моська, RF
Пользователь №: 3 863



Цитата(Mister_DSP @ Jan 20 2017, 10:22) *
Блочные коды не предлагать.

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


Цитата(Mister_DSP @ Jan 20 2017, 10:22) *
Существуют ли другие алгоритмы коррекции битовых ошибок в коротких пакетах, которые исправляют 1/4 - 1/2 числа бит от общего потока?
К примеру, из общего кодового слова длиной 24 бита исправить 6... 12 бит?
Каков предел эффективности?


:-)))))))))) Между 1/4 и 1/2 мягко говоря очень большая разница, примерно как между 1-ой космической скоростью и скоростью света :-)))))))
Можно бесконечно приближаться к 1/2, но при этом избыточность будет приближаться к 100% (из миллиона бит только 1 будет информационным, остальные проверочные).
(Не забываем, что вы просили 1/2 от ВСЕГО БЛОКА, а какова там полезная доля не сказали.)
Исправить 1/4 от всего блока уже вполне реально, но код будет длинный (десятки тысяч бит), а скорость кода будет ну где-то 1/4.

НАПОМИНАЮ:
Хорошие коды подразумевают мягенькое декодирование,
поэтому там вообще-то нет понятия "ошибки".
Ошибкой можно условно договориться считать LLR, сменивший знак.


Цитата(Mister_DSP @ Jan 20 2017, 14:22) *
я начал кое-что понимать... а именно: корректировать не испорченный пакет, а работать с группой перемежённых пакетов.
Всё ли верно?

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


Цитата(Mister_DSP @ Jan 20 2017, 14:22) *
Есть ли более эффективные коды, чем (7,4) - либо бОльшее число ошибок при заданной длине или более короткая длина на 1 ошибку?

Нет, науке не известно.
Go to the top of the page
 
+Quote Post

4 страниц V   1 2 3 > » 
Reply to this topicStart new topic
3 чел. читают эту тему (гостей: 3, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 24th March 2017 - 08:06
Рейтинг@Mail.ru


Страница сгенерированна за 0.03597 секунд с 7
ELECTRONIX ©2004-2016