Pull to refresh

Пример применения кода Рида-Cоломона

Algorithms *Wireless technologies *Programming microcontrollers *Circuit design *Sound

О чём это всё?

Всем привет! Наконец дошли руки описать то как я проверял на практике знания, полученные в ходе написания трёх статей об избыточном кодировании по методу Рида-Соломона (раз, два, три). Если лень клацать по ссылкам, то вкратце: передаём данные, к которым мы добавили некоторый оверхед, они по пути бьются, на другом конце мы их восстанавливаем, используя этот оверхед. Соль кода Рида Соломона в том, что в качестве оверхеда не нужно дублировать сообщение. Если мы добавили всего два байта, то мы можем восстановить любой испорченный байт (подробнее в статьях). Но просто написать тесты (закодировать-побить-восстановить) это ну вот совсем не интересно. Да, конечно, я написал эти тесты, они успешно прошли, но подсознательно сам себя я не убедил, что в этом может быть какая-нибудь польза. Циферки на экране. Скучно!

Как будем проверять?

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

Смотрю я и вижу: там модулируют свет лазерной указки звуком и в качестве приёмника используют солнечную панельку. Думаю, ну что за детский сад! Я ещё в пятом классе догадался приделать солнечную батарейку от поломанного калькулятора к микрофонному входу батиного усилка. А модулировал свет лазерной указки отражая его от мыльной плёнки. Говоришь в мыльный пузырь и слышишь свой голос. Даже на кассету записал - звучит смешно, высокие частоты сильно срезаны. В ту же солнечную батарейку ещё пультом от телевизора светил. Прекрасно помню тот звук цифровых данных на аудиотракте. И тут снизошло озарение. А что, если звук оцифровать, избыточно закодировать по Риду-Соломону, передать через лазерную указку, на приёмнике раскодировать и вернуть в аналог? Вот это уже интересненько. Во-первых, люблю лазеры, во-вторых, нравится ковыряться со звуком и, собственно, главное – проверим написанный алгоритм!

Как будем цифровать звук?

Ну тут, думаю, для большинства читателей не будет большой тайны как волну превратить в отсчёты. Но я не пошёл очевидным путём – использовать АЦП, встроенный в микроконтроллер. Да, надо сделать оговорку. Реализовано всё будет на стм32, самых дешёвых (когда-то, боль!) stm32f103c8, распаянных на минимальной плате, в народе её ещё называют как известные таблетки: Blue pill. Также будет использован ещё один относительно дешёвый МК stm32f411ce. Почему именно они? Да потому, что они есть в коробочке распаянные и готовые воткнуться в бредборд. Генерировать звук я решил с помощью МК. Точнее не генерировать, а воспроизводить с флешки. Не той, что USB или SD, а той, что Winbond 25q64 - микросхемка восьминогая, 4Мб, интерфейс SPI. На прекрасный способ воспроизводить звук на эстээмках меня натолкнула статья о работе с пиксельной лентой ws2812b:

Там интервалы для битовых последовательностей формируются аппаратно с использованием таймера и DMA: то есть, по окончании счёта таймера до установленного предела (регистр ARR) срабатывает DMA и загружает в регистр ширины импульса (CCR) значение из памяти, с инкрементом адреса памяти. Получается, что МК сам, без участия ЦП выдаёт импульсы и длина каждого импульса пропорциональна значению, записанному в массиве памяти. Для управления лентой там записаны длины для нулей и единиц, то есть, короткий импульс - ноль, длинный - единица. Для передачи одного бита в ленту в памяти лежит целый байт. Расточительство!

А что, если в память положить отсчёты для звука? Надо произвести маленький рассчётик. И так, у нас есть частота работы ЦП 72000000 Гц. Чтобы получился звук нужно чтобы частота отсчётов была вдвое выше максимальной частоты для звука 20000 Гц, это по теореме сами-знаете-кого (не Волан-де-Морта). Часто при кодировании эту частоту берут равной 44100 Гц. Итак, делим 72000000/44100. Получаем 1632 с копейками. Это такое максимальное значение мы можем использовать для амплитуды. Возьмём логарифм по основанию 2 и получим 10 бит на отсчёт. Обычно используют 16 бит, но у нас-то нет ЦАП на борту МК, так что придётся довольствоваться восьмибитным звуком (нет, это не звук как из денди), ведь дма не может 10 бит. Либо 8 либо 16 либо 32.

На выходе получится ЦАП, построенный на ШИМ. Частота ШИМ слышна не будет, ведь 44100 Гц мало того, что не слышны ухом, так ещё и обычный динамик так колебаться просто не сможет.

Чтобы всё получилось, в память нужно положить содержимое wav файла с частотой дискретизации 44100 и разрешением 8 бит на отсчёт (аудиофилы закрыли статью). Так как мы делаем испытание алгоритма, а не систему S/PDIF через TOSLINK, то хватит моно звука. Но памяти ОЗУ в stm32f103c8 всего лишь 20 Кб, этого хватит не всем. Примерно на полсекунды музыки. Надо выкручиваться. Тут-то я впервые применил прерывание на половине передачи DMA. Трюк в том, чтобы пока проигрывается первая половина буфера (а его размер может быть небольшим, даже 100 байт хватит) мы заполняем вторую половину, как только проигралась первая половина (а этот момент мы отлавливаем в прерывании половины транзакции) мы начинаем её заполнять новыми данными, ведь в данный момент передаётся вторая половина. В DMA мы включим циклический режим и вуаля! Вполне сносное звучание (точно все аудиофилы ушли?). В конце статьи будет небольшой видосик с демонстрацией.

Как будем передавать данные?

На физическом уровне у меня была пачка китайских лазерных модулей фирмы нонаме, что-то вроде этого (никакой рекламы и реферамы, первая, ладно третья ссылка из гугла по запросу laser diode aliexpress): Лазерные диоды. Подключать их будем через n-канальный мосфет AO3400A. Классные, кстати транзисторы. В корпусе sot23 могут через себя 5 ампер тягать, при этом стоят по рублю. Как же хорошо в современном мире!

Теперь мы можем включать и выключать лазер из программы в контроллере, что ж, никогда не думал, что напишу это на хабре, но пришло время помигать диодом! Мигать будем с использованием USART. В стм32 в усарте есть режим IrDA. Не особо много информации по этому режиму в рефмане, но, по сути, это просто усарт с другим способом кодирования нулей и единиц. И так, нам надо 44100 раз в секунду отправлять по 8 бит, это 352.8 килобит в секунду как минимум, плюс надо ещё оверхеда добавить (алгоритм же), плюс хотелось бы иметь запасик. Короче я остановился на круглом числе в 1 Мбит для усарта. CubeIDE ругается на такую частоту, и не даёт её выставить для stm32f103c8 в режиме IrDA, но он ошибается. Если руками прописать этот бодрейт в коде, то всё прекрасно заводится. При этом, кстати, для stm32f411 это, по мнению куба, вполне нормальная частота.

Метод Рида-Соломона позволяет взять некую конечную последовательность байт, добавить к ней несколько дополнительных избыточных, попортить пару, а затем восстановить. Тут нет описания потоковой передачи. Придётся городить свой метод. Я, кстати, много езжу на велосипедах ну и испытываю некую склонность к их изобретению.

Самый прямой, в лоб, метод – это разбить данные на блоки, закодировать каждый блок и слать их один за одним. если потеряется один или несколько (мало) байт, то они восстановятся. Но если в одном блоке потеряется слишком много данных, или блок будет не принят целиком, то всё, его не восстановить. Когда-то в универе нам рассказывали, и я читал где-то что в CD данные как-то режут перемешивают, и если потеряется какая-то часть подряд, то всё равно всё будет восстановлено. Потому и можно CD поцарапать, а он всё равно будет работать. Чуть-чуть подумав, я решил реализовать такую схему: допустим, у нас есть последовательность байт:

Изначальный порядок байт
Изначальный порядок байт

Разобьём их на блоки по 4, добавим к каждому блоку по 2 байта оверхеда и расположим их как таблицу, затем пронумеруем столбцы. Получится вот так:

Байты с оверхедом, столбцы пронумерованы
Байты с оверхедом, столбцы пронумерованы

Теперь мы транспонируем полученную таблицу и опять расположим данные в ряд:

Данные перетасованы
Данные перетасованы

В таком виде и будем слать данные внутри лазерного луча. Теперь если из такого ряда данных пропадёт даже значительная часть подряд, например начиная с D9 и заканчивая D6 то для каждого изначального блока это будет потеря одного или двух байт:

Побились данные при передаче. Муха, например, пролетела и закрыла луч
Побились данные при передаче. Муха, например, пролетела и закрыла луч
Каждую строку мы можем восстановить, используя избыточное кодирование.
Каждую строку мы можем восстановить, используя избыточное кодирование.

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

Для того чтобы понимать, что блок (можно называть такие блоки кадрами) принят целиком, я выбрал времннОе разделение кадров. Пауза на время двух байт. Это позволяет приёмнику не путаться, где какой кадр, и собрать назад всю таблицу - назовём её "пакетом". Также можно использовать прерывание USART IDL на приёмнике. Так код писать проще.

Как будем принимать данные?

Здесь в лоб не получилось. У меня не было никаких фотоприёмников в коробочке. Попробовал светодиод приспособить для этих целей – он не справился. Амплитуда микроскопическая на выходе и сигнал сильно смазан. Быстродействия не хватает. Сбегал в местный ЧипДип, купил всё, что у них было в наличии на тему фотоприёмников видимого света: пара разных фототранзисторов и всё. Неудача. Быстродействия не хватает (мегабит, ведь, помним?). Купил фотодиод для инфракрасного света, вот такой. Не обманули. Для инфракрасного излучения работает как положено. На прямой свет красного лазерного диода не реагирует от слова совсем. Но это достигается за счёт пластикового корпуса, который задерживает видимый и пропускает ближний инфракрасный. Хм, у меня ведь есть напильник! Сточил часть корпуса, которая со стороны кристалла,

Немного обработать напильником
Немного обработать напильником

смотрю на осциллограф - Всё именно так, как и хотелось бы. Амплитуда маленькая, но форма сигнала вполне себе норм. Можно было бы заказать фотодиод для видимого света, конечно же. Но хочется здесь и сейчас. А это напильник.

Дальше. Амплитуда маленькая, а надо, чтобы было 0 и 3.3 В для того, чтобы это подать на ножку контроллера. Плюс смещение, которое меняется в зависимости от внешнего освещения. Придётся аналогово схемотехничить. Если аналогово, то ОУ. Если ОУ, то LM358. Не я это придумал, так повелось испокон веков. Подсоединяю... Ага. Граничная частота единичного усиления 1 МГц. Единичного. А надо в 300 раз увеличивать. Не годится. Чуть получше NE5532P 10 МГц единичного усиления. Пробую, не работает как надо. Пришлось купить подороже LM6172IN. 100 МГц единичного усиления. Уже получше. Для наглядности: форма сигнала на двух последних:

Синий луч – это входной сигнал, жёлтый – выходной после усиления в 10 раз. Слева медленный ОУ, справа быстрый. Ещё в 30 раз усиливает второй каскад. Получаются очень даже прямоугольные, красивые импульсы. Их я не заснял. Также, между каскадами поставил дифференцирующую RC цепочку. Она прекрасно компенсирует внешнее освещение. Работает и в темноте, и на солнце. Ещё нюанс: Этому ОУ нужно двухполярное питание. Его я организовал с использованием ОУ. LM358 опять не справился. Пришлось поставить NE5532P. Схема всего этого безобразия получилась такая:

Инвертер на выходе нужен для того, чтобы работал USART в режиме IrDA. Там требуется инверсный сигнал. Для питания логики используется LDO, чтобы согласовать уровни пришлось ещё одну RC цепочку поставить. Конечно, можно было бы соорудить намного более совершенную схему, но эта собралась из того, что есть в коробочке, на бредборде и со своей задачей справляется.

Как будем раскодировать?

Тут всё довольно-таки просто. USART в режиме DMA складывает данные в буфер. По прерыванию IDL данные из этого буфера, согласно своему порядковому номеру (блоки пронумерованы), помещаются в нужное место в пакете. Если вместо номера кадра там какое-нибудь непонятное значение, мы запоминаем номер этого кадра как битый. Как только пакет принят полностью мы его транспонируем и проверяем алгоритмом каждую строку на предмет целостности. Если синдром не нулевой, то исправляем используя всю мощь алгоритма Рида-Соломона. Затем копируем данные без оверхеда в буфер для проигрывания.

Тут возникает небольшая проблемка. Частоты приёмника и передатчика ну никак не совпадают. Обязательно будет небольшая разница. Для разрешения этой проблемы я сочинил такой механизм: Пакеты на передатчике отправляются по мере заполнения. На нём данные идут одновременно и в проигрывание (это при разработке я сначала проигрывание в передатчике организовал) а также в буфер для передачи. Как только набирается целый пакет он кодируется и отправляется. В приёмнике я контролирую, на каком моменте проигрывания буфера приходит новый пакет. При полном совпадении частоты это был бы один и тот же момент для каждого пакета. В грубом и несовершенном мире момент плывёт во времени. Вот эту разницу я задал как вход П-регулятора (софтверного, конечно же). А выход – это скорость воспроизведения на приёмнике. Её можно чуть-чуть регулировать, слегка изменяя период ШИМ, это тот который должен быть с частотой 44100 Гц. Прикольный эффект от этого. Если пакет целиком теряется, то П-регулятор сбивается и начинает ускорять или замедлять звук ненадолго. Эффект похож, как когда в магнитофоне моторчик механизма притормаживаешь чуть-чуть.

Как воспроизводить?

В главе про оцифровку я рассказал метод генерации звука на STM32. На выходе получается ШИМ сигнал с частотой 44100. Его можно просто подключить к динамику или наушнику и там будет вполне себе слышно то, что нужно. Если сильно хочется, то можно поставить RC ФНЧ и развязывающий конденсатор. Дальше делителем можно привести к амплитуде в 1В и отправить на вход усилителя. Мне хочется, чтобы без внешнего усилителя и всё работало. Преимущество такого сигнала в том, что его можно усиливать в ключевом режиме. Вроде бы это называется усилитель D-типа, но это неточно. К выходу усилителя я прицепил опять AO3400A через оптопару (звук опять передаётся через оптику) по такой схеме:

Без оптопары шли помехи на усилитель приёмника. А так работает всё.

Для передающей части у меня бредборда не нашлось, так что она получилась в таком виде:

На принимающей части ещё есть дисплей для отображения статуса приёма. Было сложно сочинить как информативно в реальном времени отображать статус приёма. Остановился на количестве принятых пакетов всего, количестве битых пакетов и количестве битых кадров в последнем битом пакете. Демо видео:

И к чему это всё?

Две пользы. Показать широкой (ага, прям мильёнам) публике, что можно сделать с помощью недорогих, относительно современных микроконтроллеров, и, конечно же, получить бесценный опыт. Довольно-таки много разных технологий задействовано в этом проекте. Исходный код... Да. Вот бывает стыдно позвать гостей в квартиру, когда не прибрано. Так и с исходным кодом этого проекта. Делалось ведь не по работе и не в коммерческих целях, так что извините. Исходники кодировщика Рида-Соломона есть в статьях об алгоритме (ссылки в самом начале). Там на Си шарп, но очень легко портировать на C++. Всё. Спасибо!

Tags:
Hubs:
Total votes 102: ↑102 and ↓0 +102
Views 17K
Comments Comments 45