Comments 46
Неплохо. Можно в качестве лабораторной для студентов или старших школьников прменить, возьму на воружение.
По поводу последовательности: корректирующие коды расположены целым блоком, и если именно они испорчены, то зафейлится очень большой кусок данных, в этом случае, вы данные выкидываете или играете как есть? Возможно, корректирующие коды тоже надо как-то распределить?
Второй момент, поскольку речь идёт о звуке, а в нём важна скорость изменения, а не абсолютные значения, то, возможно, имеет смысл кодировать уровни кодом, при котором соседние значения изменяются на 1 бит (в обычном счёте 1000 и 0111 соседи, но отличаются на 4 бита), тогда лёгкие помехи не будут сильно искажать амплитуду.
Ну и третий момент: восстановление с помощью корректирующих кодов, тоже может давать ложные данные, хотелось бы статистику, то есть записать принятые данные, а потом сравнить с первоисточником и показать реальную эффективность не только восстановления, но и искажения. Собственно, иначе не было бы такого класса как контрольные суммы, их бы просто вытеснили корректирующие коды, ан нет, не всё так просто.
Ну и ещё один момент, как вы справедливо заметили тайминги приёмника не совпадают с таймингами отправителя, кроме того, среда так же может растягивать или спрессовывать во времени сигнал, поэтому отправив 1111 такое, просто посчитав длительность этого монолитного сигнала, в общем случае, нельзя сказать 111 или 11111 было изначально, для этого каждый бит передаётся сигналом, переходящим через ноль, не зависимо от того, еденица это или ноль, таким образом, обходятся фундаментальные проблемы, которые на первый взгляд не видны.
восстановление с помощью корректирующих кодов, тоже может давать ложные данные, хотелось бы статистику, то есть записать принятые данные, а потом сравнить с первоисточником и показать реальную эффективность не только восстановления, но и искажения
До тех пор, пока интенсивность помехи не превосходит восстанавливающую способность кода — ложные данные получить невозможно. Мы же введением кодов — расширили пространство передаваемых сообщений, при этом большУю часть точек вновь созданного пространства объявили запрещенными. И если принятое сообщение попало в запретную область — то мы своей функцией расстояния на вновь введенном пространстве определим ближайшее корректное сообщение — и к нему скорректируемся.
А если помеха смогла перевести одну корректную точку пространства расширенных состояний — в другую, то у нас либо неправильная модель помехи, либо недостаточна заложенная под модель помехи избыточность кода… Но уж эту проблему довольно легко решить — добавление хеша сообщения (в простейшем случае — CRC16/32) до применения избыточного кода и проверка — после декодирования. Это очень дешевый способ отбрасывать испорченные сообщения (и свалить проблему на протоколы высших уровней...), но никак не помогающий их таки-передавать. А помехоустойчивые коды дают возможность именно протолкнуть сообщение по физическому каналу связи с любыми (!) наперед заданными помехами — при условии, что вы готовы оплатить накладные расходы в виде дополнительных бит данных…
Как выше заметили, в передаче самого кода вероятны ошибки - притом настолько же вероятны, как и в исходном сообщении, так что пользы в данной реализации от кода восстановления немного. Например, если длина кода совпадает с длиной сообщения, то их вероятности повреждения равны, а поскольку хэш суммы в данной реализации нет, то добавление кода удваивает размер сообщения и тем увеличивает вероятность повреждения сообщения с кодом (если вероятность передачи без ошибки исходного сообщения 0.5, то для удвоенного сообщения эта вероятность равна лишь 0.5*0.5=0.25). Автор не посчитал помехоустойчивость для варианта с его кодом восстановления и без него для разной вероятности ошибки, в итоге эта реализация бесполезна и вредна - простое дублирование сообщений с хэш суммой будет работать надежнее (и намного быстрее обрабатываться на передатчике и приемнике). И, кстати, при помехе типа пролетевшей птицы (как в статье предложено) опять же оптимальным будет именно простое дублирование.
Однако, бОльшая часть подобных кодов родилась из радиосвязи (или передаче сигнала по проводам) — и имеет в качестве модели помехи статические разряды (молния где-то ударила, рубильник поближе включили и т.д.). Этот вид помех характеризуется малым временем действия, но широким спектром, от которого практически невозможно отстроиться стандартными способами фильтрации сигнала. Собственно, под это вам коды и даны — крайне редкое (по сравнению с временем передачи пакета) событие, необратимо меняющее некоторое количество бит в одном пакете. Соответственно, вы задаетесь средней длительностью static event, делите ее на скорость передачи — и получаете количество бит, которые будут испорчены. И выбираете код с нужной корректирующей способностью.
Если же вы полагаете, что увеличение длины сообщения увеличивает и вероятность его повреждения, и поэтому коды в пределе перестают работать — то это заблуждение. Теорема Шеннона утверждает, что для канала с помехами всегда можно найти такую систему кодирования, чтобы снизить веротяность ошибочного декодирования передаваемой информации до любой бесконечно малой величины. Потому что добавление одного бита избыточности — увеличивает длину сообщения, собственно, на один бит — но удваивает размерность пространства сообщений. В пределе — размерность пространства (и восстанавливающая способность) будет расти невообразимо быстрее, чем вероятность появления второго static event во время передачи удлиненного пакета.
Также, нельзя считать, что обнаружение и исправление ошибок всегда можно переложить на протоколы верхних уровней. В некоторых случаях, на объекте вообще может быть только приемник. Или, как в дальнем космосе — передатчик есть, но использовать его дорого с точки зрения расхода бортовых ресурсов, да и задержка… Или цена неправильной дешифровки сильно велика (например, у военных). Или верхний протокол уже не может учесть особенности канала связи…
В общем, мое мнение — коды коррекции ошибок нужно уметь для общего развития. И осваивать их легче на игрушечных задачах. Собственно, про уровень лабораторной работы в комментариях уже неоднократно говорилось. Я склонен такое творчество поддерживать — оно дает понимание не на уровне прочтенного учебника, и не на уровне списанной методички, а реально через руки. И это уже надолго…
Спасибо, выразили словами цель проекта. Через руки - всё верно.
Если же вы полагаете, что увеличение длины сообщения увеличивает и вероятность его повреждения, и поэтому коды в пределе перестают работать — то это заблуждение.
Помехи бывают разных типов и оптимальное кодирование для одного типа может вовсе не работать для другого. У автора достаточно единственной ошибки в коде восстановления, и при любой длине кода сообщение будет повреждено. Разумеется, длина кода увеличивает вероятность ошибки в нем. Выше уже ведь писали про хэш сумму, но автор так ничего и не понял. Это именно непонимание базовых принципов - Шеннон изучал оптимальные коды, а не произвольно придуманные без оценки оптимальности. Именно поэтому без оценки точности восстановления от длины последовательности и кода восстановления это похоже на попытку создать "боинг" из мусора методом тыка. Так что эта статья учит неправильно, увы, хотя автор обещает именно научить.
Теорема Шеннона утверждает, что для канала с помехами всегда можно найти такую систему кодирования, чтобы снизить веротяность ошибочного декодирования передаваемой информации до любой бесконечно малой величины.
При бесконечном времени передачи это можно сделать и просто повтором сообщения с хэш суммой - а без нее вы никогда не узнаете, получено ли исходное сообщение с требуемой достоверностью. Попробуйте в снегопад передавать информацию лучом лазера - реальная задача создания оптической меш-сети для города. Это возможно и лет 20 назад я как раз работал с командой в университете ННГУ над таким проектом для компании LG, так что никак не разделяю ваши шапкозакидательные настроения.
Второе — вам бы все-таки желательно посмотреть теорему Шеннона и выводы из нее. То, что бесконечным повторением одного сообщения можно его протолкнуть через канал с помехами — было очевидно и до него. Шеннон показал, что по каналу с помехами (причем накладывая довольно слабое условие — корреляцию входа и выхода канала) можно за конечное время протолкнуть сообщение с любой сколь угодно малой вероятностью ошибочного декодирования. Это намного более сильное утверждение, чем «при бесконечном повторении...». До тех пор, пока интенсивность ваших сообщений не превышает пропускной способности канала (а она как раз определяется корреляцией входа и выхода) — вы всегда сможете подобрать нужный код. Важно, что коды Рида-Соломона являются оптимальными в большом классе кодов, для которых выполняется предел Рейгера. Любой другой код, добавляющий такую же избыточность — не сможет исправить больше ошибок чем Рид-Соломон.
Третье — не оспаривая ваш практический опыт, скажу что помехоустойчивое кодирование и контроль целостности сообщений являются двумя разными проблемами. Как правило, их решают на разных уровнях (кодирование — ближе к физическому уровню передачи, контроль целостности — ближе к сетевым протоколам), и одно другого не заменяет. Если же вы считаете, что с практической (!) точки зрения применение кодов РС в задаче автора статьи не имеет смысла — я уже выше писал, что вы правы. Это учебно-тренировочная задача, и выхлоп от нее получается в основном в голове решающего. Весь остальной антураж — это модель, позволяющая перевести знания о корректирующих кодах — в умение их применять. А между «знать» и «уметь» — большая разница…
ежели добавлено 2t бит, то ошибки в любых t битах будут исправлены...
Для рассматриваемой реализации - если сообщение из 100 бит передано корректно, а последующий блок 200 бит кодов восстановления поврежден полностью, в рассматриваемой реализации итог - все сообщение повреждено полностью. И ошибок нет, но сообщение передать невозможно - такая вот реализация. Вы разницу между теорией и практикой понимаете?
До тех пор, пока интенсивность ваших сообщений не превышает пропускной способности канала (а она как раз определяется корреляцией входа и выхода) — вы всегда сможете подобрать нужный код.
Как это применимо к выбранному автором наугад коду из статьи без проверки его характеристик? Именно об этом я выше и писал - рассматриваемый код выбран наугад и он, очевидно, совершенно не оптимален. Смысл работы Шеннона как раз в построении оптимального кода и методологии его оценки, автор же ссылается на Шеннона, но делает наугад негодный код. За Шеннона обидно (с)
А код автор делает ровно такой, какой хочет изучить и потрогать. Понимаете — у большинства людей (и у меня, например, тоже) есть только один способ перейти от знания к умениям — и он называется практикой. Когда я прочитал о чем-то — мне кажется, что я понимаю. Однако, жизненный опыт показывает, что на самом деле понимание еще не пришло, и оперировать вновь усвоенными знаниями я пока мало способен. Поэтому берется какая-то довольно простая задача с применением новых понятий — и делается попытка ее решить. Эта задача не должна быть слишком сложной — чтобы во-первых, был шанс ее решить за разумное время и не распыляться на сложности не связанные напрямую с изучаемым эффектом. А с другой — достаточно сложной, чтобы было очевидно если она решена неправильно. В данном случае автор сделал минимально возможную схему из «желудей и палок», которая дает ему канал связи и наглядный payload в виде звука. Если коды будут построены правильно — он услышит на выходе переданные звуковые данные, и сможет проверить, например, пределы корректирующей способности кода. Это не собираются ставить в реальное оборудование для связи или на спутник, блин… Я реально не понимаю, чем вы таки недовольны?.. :-(
Я реально не понимаю, чем вы таки недовольны?.. :-(
А вы не находите, что это чистый кликбейт - выдавать любой наугад придуманный способ кодирования (притом, что добавление избыточности в этой реализации ухудшает результат передачи) за оптимальный код Шеннона? А ведь многие прочитавшие поверили автору, судя по комментариям.
Спасибо за активность в комментариях)) Ведь про "ухудшение", вы ведь сами понимаете, полный бред. На видео: нет коррекции – слышны помехи. Коррекцию включаем – помехи исчезли.
У автора достаточно единственной ошибки в коде восстановления, и при любой длине кода сообщение будет повреждено.
Это не так. Коды коррекции ошибок позволяют восстановить сообщение после порчи какого-то символов в любом месте закодированного сообщения, неважно попадут они в данные или в сам код коррекции. Иначе от них было бы мало пользы: редко когда у нас есть ненадёжный канал для данных, и при этом надёжный канал для кодов коррекции.
У автора достаточно единственной ошибки в коде восстановления, и при любой длине кода сообщение будет повреждено.
Это неверное утверждение. Код Рида-Соломона таков, что не важно в каком символе ошибка. Даже если эта ошибка в избыточном коде, то, несмотря на то, что само сообщение не повреждено, ошибка будет детектирована и исправлена. Почитайте про Рида-Соломона. Там даже софтинка есть - можно взять сообщение, дополнить избыточно, повредить любую часть, включая избыточные символы и восстановить.
это можно сделать и просто повтором сообщения с хэш суммой - а без нее вы никогда не узнаете, получено ли исходное сообщение с требуемой достоверностью.
Ещё раз про хеш. Код Рида-Соломона также может быть использован как хеш. И достоверность также вычисляется.
Код Рида-Соломона ...
Вы апеллируете к авторитету, хотя реализация потоковой передачи здесь "самопальная":
Тут нет описания потоковой передачи. Придётся городить свой метод.
Вот тут все и ломается.
Пауза на время двух байт. Это позволяет приёмнику не путаться, где какой кадр...
Выше я приводил пример помех - снежинки. Отдельные импульсы выпадают целиком, рассеиваясь на снежинках (одной или нескольких), и ничего работать не будет.
По поводу первого пункта: если портятся коды коррекции то алгоритм работает также, как если бы портились сами данные - в статьях про это есть.
По поводу способа передачи, то была важна не передача звука, а проверка-демонстрация работы алгоритма
По поводу ложных восстановлений - в статьях о кодировании есть расчёт вероятности такого события. Она ничтожна. Корректирующие коды в отличии от контрольных сумм требуют довольно-таки немалого вычислительного ресурса.
По поводу NRZI, о котором вы упомянули, эта мысль мне тоже пришла в голову. Только вот реализация подкачала. В STM32 нет NRZI выхода. Я попробовал сфтверно его реализовать, но скорости выше 100КБит таким способом не добьёшься, а надо Мегабит.
Вы никак не поймете, что вероятность повреждения данных пропорциональна их размеру, так что эта вероятность для последовательности из данных плюс (в статье - почти такой же длины) кодов восстановления намного выше, чем вероятность порчи только данных. Поскольку без хэш суммы нельзя определить, что именно повреждено, то применение поврежденных данных и/или кодов восстановления в любом случае портит результат. Это и есть причина, почему на практике не делают длинных кодов восстановления и добавляют хэш сумму данных. Еще раз - посчитайте помехоустойчивость в зависимости от длины кода восстановления и сравните с помехоустойчивостью без кодов и с дублированием сообщения при наличии хэш суммы.
Инвертер на выходе нужен для того, чтобы работал USART в режиме IrDA
Поменяйте местами VD1 и R5, и инвертор с ЛДО станет не нужен. Или подавайте сигнал на инверсный вход второго операционника.
Да и не понятно, зачем в каждом каскаде усиливать постоянную составляющую, что бы её потом срезать разделительным конденсатором?
Это я попробую, спасибо! Ведь точно знаю, что усиление можно сделать намного более эффективным, ведь в системах с инфракрасным пультом всё работает с намного более слабыми сигналами, а не направленным лучом.
И, до кучи, — ещё по схемотехнике:
Для питания логики используется LDO
FTGJ — 78L05 ни разу не LDO.
К выходу усилителя я прицепил опять AO3400A через оптопару (звук опять передаётся через оптику) по такой схеме:
Без оптопары шли помехи на усилитель приёмника.
Странная схема…
ШИМ — без фильтра. Может поэтому и помехи? Или из-за самоиндукции на обмотке динамика?
Затвор N-канального(?) полевика намертво на плюсе. Но что-то пытается на него податься через оптрон и резистор аж в 1 кОм.
В передаче данных с помощью (А)DSL точно такой же трюк - транспонирование матрицы с данными дополненной кодами, используется.
много езжу на велосипедах ну и испытываю некую склонность к их изизобретению
Ваш новый велосипед похож на Forward Error Correction FEC, используемый в частности для транспорта мультимедиа контента.
Идея статьи интересна, хоть и не нова. Но все портит то, что суть статьи не подтвердить/опровергнуть теорию, а изобретение велосипеда и ходьба по граблям.
Хотя бы для интереса посмотрите как реализовано это в обычных cd проигрывателях. Начиная от кодирования, заканчивая схемотехникой.
Как я понимаю, вы использовали код (6, 4) над полем GF(2^8) и перемежение при передаче?
Ну и ещё несколько вопросов/комментариев для уточнения:
1. Почему был выбран именно (6, 4)?
2. Я правильно понимаю, что для декодирования вы использовали Берлекемпа из предыдущей статьи? Не думали про Питерсона (ПГЦ, PGZ)? Для кода, исправляющего одну ошибку, он, как мне кажется, проще и быстрее.
3. Раз уж вы всё равно собираете данные в таблицу, можно было бы использовать каскадный код — кодируем и по строкам, и по столбцам.
4. Не думали про коды над более коротким полем? Тем же GF(2^4). При том же общем битовом размере получился бы код (12, 8) с исправлением не одной 8-битовой, а двух 4-битовых ошибок (символьных, конечно же, а не произвольных). Декодер и кодер чуть сложнее (надо дополнительно бить каждый байт на два символа), зато умножитель проще.
Не совсем так. (6, 4) - это для наглядности в статье. Реально использую (48, 32) это максимум, на который хватает быстродействия. Для декодирования - да. Берлекэмп. Какая-то из эффективных реализаций. Если делать блоки меньше, то пропадает выигрыш от использования dma при приеме-передаче. Так или иначе у меня теперь есть код, который можно применить, если вдруг понадобится что-нибудь избыточно закодировать. Например rs485 между какими-нибудь промышленными блоками. Там резкая случайная помеха не редкость.
Реально использую (48, 32) это максимум, на который хватает быстродействия.
Тогда не очень понял. Вы сейчас рассматриваете код как битовый, т.е. n=(6*8=48 бит) и k=(4*8=32 бита), или символьный, т.е. n=48 байт (символов конечного поля GF(2^8)) и k=32 байта?
Второй вариант, 32 полезных, 16 избыточных, всего 48.
Хм. Даже не думал, что STM такой код потянет с приличной производительностью.
А умножитель делали логарифмический табличный через два предварительно рассчитанных массива и операции с памятью?
Логарифмы, естественно. Конечно можно было бы 65536 байт выделить и ещё чуть ускорить. Память f411 позволяет. И да, не 8 ошибок, а больше, ведь я могу ещё ориентироваться на номер битого кадра, если, например, мне приходит кадр с номером 21, а за ним номер 25, то я могу стопроцентно сказать, что во всех кадрах после транспонирования байты с 22 по 24 битые
ещё в пятом классе догадался приделать солнечную батарейку от поломанного калькулятора к микрофонному входу батиного усилка. А модулировал свет лазерной указки отражая его от мыльной плёнки. Говоришь в мыльный пузырь и слышишь свой голос
А вот про это можете поподробнее рассказать, пожалуйста? Там лазер отражается от пузыря, который колеблется от звука голоса? Полностью отражается на солнечную панель или часть проходит/преломляется через пузырь, вот эту часть не могу представить. У этого есть какое то название чтобы можно было найти в интернетах или чисто Ваша детская забава?
К сожалению, мой пятый класс был довольно-таки давно. Тогда не было у меня ни интернета не компа -- развлекался чем мог)) Из-за того, что поверхность мыльной плёнки искажается под действием звука, то меняется форма и площадь отраженного пятна лазера, а так как меняется площадь, то меняется и интенсивность. Работает всё тем лучше, чем дальше детектор от пузыря. Но сколько-нибудь заметно плёнку искажают лишь низкие частоты потому и звук получался как из .. ну неважно. Похожий трюк проделывал Дастин с канала smarter every day. Там он снимал колебание чего-то лёгкого на очень высокоскоростную камеру, а затем из видео звук извлекал.
Спасибо, вспомнил детство, когда брал в библиотеке радиоежегодники и читал про устройство CD и DAT.
А раньше линки на указках между домами поднимали. В связи с новыми реалиями, копеешные mesh сети из окна в окно.
Большое спасибо за данный цикл статей!
Пример применения кода Рида-Cоломона