[Перевод] Фонтанные коды и динамические QR-коды

задняя часть Программа перевода самородков

Фонтанный код и динамический QR-код

fountain

(Источник изображения:Anders Sune Berg)

существуетпредыдущий пост, я объясняю проект, который я завершил на выходных:txqr, в котором используется последовательность динамического QR-кода, которую можно использовать для односторонней передачи состояния. Самый простой и прямой метод — повторять закодированную последовательность данных до тех пор, пока приемник не получит полные данные. Такого простого повторяющегося кода достаточно для начала обучения новичков, и он прост в реализации, но в схему также вводится определенная задержка, чтобы приемник не пропустил ни одного кадра информации.В процессе практического применения ситуация пропуска часто встречается информация.

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

В комментариях к предыдущему посту,Bojtos KiskutyaУпомянуты коды LT, которые позволяютtxqrПолучите лучшие результаты. Именно такие комментарии я бы хотел видеть — не только предложения по оптимизации, но и возможность открыть для себя что-то новое и интересное. Поскольку я никогда не сталкивался с кодированием LT, я сделал все возможное, чтобы узнать об этом в ближайшие несколько дней.

Так что я знаю,LT codes(LTпредставляет собой преобразование рупии (Luby Tсокращение для преобразования)) является более крупной кодировкой:фонтан дворреализация . этоКодирование стиранияДля корректного декодирования информации достаточно класса, в котором он может генерировать бесконечное количество блоков данных из блоков исходной информации (К), и он получает немного больше информации, чем К закодированных блоков. Получатели могут начать получать блоки с любой позиции, в любом порядке и могут устанавливать произвольные вероятности стирания — когда вы получаете более K различных блоков, код фонтана может начать работать. Собственно, отсюда и произошло название «фонтан» — мы сравниваем действие наполнения ведра с получением сообщения, а действие фонтана, извергающего капли воды, похоже на отправку серии закодированных блоков, другими словами, вы можете заполнить ваше ведро с какой каплей воды вы получаете.

Это как нельзя более подходит для моего проекта, поэтому я быстро поискал реализацию на основе Go:google/gofountain, и заменил мой предыдущий рудиментарный перекодированный код реализацией преобразования рупии. Результаты тестирования после замены кода очень хорошие, поэтому в этой статье я поделюсь некоторыми подробностями алгоритма LT и используюgofountainТам, где пакет подвержен ошибкам, в конце я также приведу сравнение окончательных результатов тестирования двух кодов.

Код фонтана потрясающий!

Если, как и я, вы никогда не слышали о фонтанных кодах, не беспокойтесь — поскольку фонтанные коды все еще являются относительно новой технологией, они могут решить лишь небольшое количество очень специализированных задач. Но фонтанные коды на самом деле довольно крутые. Он идеально сочетает в себе случайность, математическую логику и распределение вероятностей для достижения своей конечной цели.

Хотя я в основном рассматриваю LT-кодирование, в этой системе кодирования есть много других алгоритмов, таких какOnline codes,Tornado codes,Raptor codesПодождите, коды Raptor превосходят почти во всем, кроме легальности. Но все они, похоже, защищены строгими патентами, поэтому широко не используются.

Принцип кодирования LT относительно прост — кодер разбивает информацию на несколько частей.блок исходной информации, а затем продолжить созданиеблок кодирования, эти закодированные блоки содержат 1 или 2 блока исходной информации или более случайный выборблок исходной информацииИ XOR все выбранные блоки исходной информации, чтобы получить вывод. для создания каждого новогоблок кодированияИдентификатор хранится в нем случайным образом.

lt encoder

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

Итак, когда декодер получает только одинблок исходной информациисостоит изблок кодирования- он просто добавляет его в очередь декодируемых блоков, никаких других действий не требуется. и если он получает использование двухблок исходной информацииXOR составляют быстрые кодировки, а декодер проверяет идентификаторы, с которыми они были переданы, и если один из них уже стоит в очереди на декодирование — то в зависимости от характера операции XOR восстановить кодировку довольно просто. декодировать более двухблок исходной информациисостоит изблок кодированияТо же самое верно - как только вы можете получить декодированный блок, просто продолжайте выполнять операцию XOR.

Солитонное распределение

Круто то, как выбрать, сколько блоков кодирования делает только одинблок исходной информациикодирование, и сколько сделано с двумя или болееблок исходной информациизакодировано. Если у вас слишком много пакетов блочного кодирования из одного источника, вы можете потерять необходимую избыточность. И если есть слишком много пакетов, закодированных фрагментами из нескольких источников, то получение фрагмента из одного источника на зашумленном канале займет слишком много времени. Отсюда и название кодировки Luby,Michael LubyсказатьСолитонное распределениеЭто почти самый совершенный метод распространения для решения этой проблемы, он может гарантировать, что вы получите достаточное количество пакетов кодирования информационных блоков из одного источника, а такжеполно, который также имеет очень длинную мантисса и может использоваться для пакетов с блочным кодированием с несколькими источниками вплоть до пакетов с блочным кодированием из N-источников, где N равноблок исходной информацииколичество.

solition distribution

Вот более четкое представление данных заголовка дистрибутива:

solition distribution zoom

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

Все эти свойства придают LT-кодированию характеристику, не зависящую ни от частоты передачи, ни от режима скорости потери пакетов в канале связи.

Для моего проекта txqr это означает, что использование фонтанных кодов сокращает среднее время кодирования независимо от параметров кодирования и передачи.

гугловский фонтан

Пакет gofountain, разработанный Google, реализует несколько кодов фонтана в Go, включая коды преобразования Luby. этоAPI очень легкие(хороший знак для библиотеки) - в основном содержит толькоCodecинтерфейс и некоторый код реализации,EncodeLTBlocks()функцию, а некоторые вспомогательные функции — как генераторы псевдослучайных чисел.

Однако, пытаясь понятьEncodeLTBlocks()Я немного смущен, когда дело доходит до того, что означает второй аргумент:

func EncodeLTBlocks(message []byte, encodedBlockIDs []int64, c Codec) []LTBlock

Зачем мне передавать идентификатор блока кодировщику, я даже не хочу заботиться о других свойствах блока, так как реализация алгоритма должна быть заботой самой библиотеки, а не пользователя библиотеки. Так что сначала я догадался просто передать все ID блоков -1..N.

Моя догадка близка к истине — отладочный вывод теста кодирует фрагменты так, как я хочу, но процесс декодирования не всегда выполняется правильно.

Я проверилСтраница документации для gofountain, хотел посмотреть, какие другие пакеты его используют, и нашел библиотеку с открытым исходным кодом для передачи больших файлов в сетевых средах с потерями —pump, автор которогоSudhir Jonathan, поэтому я решил воспользоваться дружественным сообществом Gopher и попытался связаться с Sudhir в slack Gopher, чтобы спросить, может ли он помочь мне понять, для чего нужны эти идентификаторы.

Позже мне удалось связаться с Судхиром, он дал мне очень подробные ответы и развеял все мои сомнения, что мне очень помогло. Правильный способ использования этой библиотеки — последовательная отправка идентификаторов блоков в порядке возрастания, например,1..N,N..2N,2N..3Nи Т. Д. Поскольку в общем случае мы не знаем уровень шума канала, очень важно всегда генерировать новые блоки данных.

Таким образом, правильным использованием этих идентификаторов было бы создание блоков идентификаторов в цикле и вызов их в цикле.EncodeLTBlocksфункция. Но чтобы это работало, мне нужно было убедиться, что кодирование QR-кода достаточно быстрое, чтобы генерировать новые фрагменты данных на лету. При скорости 15 кадров в секунду общее время кодирования следующего блока данных и генерации нового QR-кода должно быть менее 1/15 секунды или 66 мс. Очевидно, что это работает, но его необходимо тщательно протестировать и оптимизировать, чтобы убедиться, что это верно и для одноядерных версий, транспилированных с помощью GopherJS, в браузере.

Кроме того, в настоящее время существуют некоторые конструктивные ограничения -txqr.Encode()Ожидается, что API вернет определенное число, указывающее, сколько блоков будет закодировано в виде кадров QR-кода, иtxqr-testerАнимированные файлы GIF генерируются для обеспечения надежности частоты кадров во время работы браузера, поэтому я решил, что пока лучше не ломать API и использовать метод с коэффициентом избыточности.

Метод коэффициента избыточности основан на предположении, что в моем проекте шум в некоторой степени предсказуем — пропуск кадров не более 20%. мы можем генерироватьN*redundancyFactorкадр, а затем цикл, как подход кода цикла, который неоптимален в обычных случаях, но для нужд моего проекта и контролируемых внешних условий этого достаточно. Так оencodedBlockIDsПараметры, я использовал простую вспомогательную функцию:

// ids 函数使用 0..n 中的值生成多个 ID 切片
func ids(n int) []int64 {
    ids := make([]int64, n)
    for i := int64(0); i < int64(n); i++ {
        ids[i] = i
    }
    return ids
}

Вызывается следующим образом:

    codec := fountain.NewLubyCodec(N, rand.New(fountain.NewMersenneTwister(200)), solitonDistribution(N))

    idsToEncode := ids(int(N * e.redundancyFactor))
    lubyBlocks := fountain.EncodeLTBlocks(msg, idsToEncode, codec)

не заинтересован вgofountainЧитатели , эта часть может быть несущественной и несколько скучной, но я надеюсь, что она будет полезна тем, кто также запутался в этом API, чтобы они могли найти эту статью через результаты поиска.

Результаты теста

Поскольку я сохранил API исходного пакета, остальное было легко. ты можешь помнитьпредыдущий пост, мое веб-приложение использует файл с именемtxqr-testerПакет Go для проекта txqr, который запускается в браузере. И здесь меня снова вдохновляет кроссплатформенность Go! Мне просто нужно переключиться на тот, который включает новую реализацию кодирования и декодированияfountain-codesветка, бегgo generateвыполнитьgomobileиgopherjsкоманду, и всего через несколько секунд приложение Fountain Code будет готово к использованию в Swift и браузере.

Я думаю, боюсь, ни один другой язык не может этого сделать?

Далее я запустил тестовую программу, включающую запуск мобильного телефона на штативе и внешнем дисплее, настройку параметров теста и запуск автоматического теста, этот процесс продлится почти полдня. В этот раз я не стал изменять уровень ошибки QR-кода для экономии времени, потому что кажется, что влияние этого параметра на результат в принципе незначительно.

Результаты меня шокировали.

Время, записанное для тестовой передачи около 13 КБ данных, теперь составляет всего полсекунды, если быть точным.501ms- Скорость передачи близка к 25kbps. Этот набор записей настроен на 12 кадров в секунду, 1850 байт информации на QR-код и низкий уровень исправления ошибок. Разница во времени, необходимая для декодирования, значительно уменьшена, поскольку в этой версии отсутствуют «требующие повторения цикла» и повторяющиеся части кода. Вот сравнениеповторяющийся кодифонтан дворГистограмма времени декодирования:

time_histogram

Как видите, большая часть тестового времени декодирования, сконфигурированного с разными значениями FPS и размера блока, сосредоточена в меньших числах на временной шкале — большинство из них составляет менее 4 секунд.

Вот более подробный результат:

time_vs_size

Результаты тестов были отличными, поэтому я решил запустить тесты с чанками больше 1000 байт — размером до 2000 байт. Это дало мне очень интересные результаты: многие тесты с размерами блоков от 1400 до 1700 байт прошли по тайм-ауту, но результаты для блоков от 1800 до 2000 байт, безусловно, наилучшие:

time_vs_size_2k

В этом тесте эффект FPS кажется еще более незначительным, но он дает лучшие результаты из всех конфигураций, и я даже могу поднять его до 15FPS:

time_vs_fps

Вот полный интерактивный 3D-график результатов теста:

3d_results

в заключении

Использование кода фонтана, безусловно, захватывающая вещь. Это гениально, но просто, и хотя это небольшой объем, он очень полезен, умен и быстр, и они определенно являются частью «крутого алгоритма». И как только вы поймете, как они работают, они станут одним из тех алгоритмов, которыми вы восхищаетесь.

Для проекта txqr они также обеспечивают повышение производительности и надежности, и я с нетерпением жду возможности использовать алгоритмы, которые более эффективны, чем кодирование LT, и реализовать API, которые можно адаптировать к функциям потока исходного кода.

А Gomobile и Gopherjs еще раз демонстрируют свою удивительную сторону, максимально сводя к минимуму проблемы с использованием кода, который был написан и протестирован в браузерах и мобильных платформах.

Ссылка на ссылку

Если вы обнаружите ошибки в переводе или в других областях, требующих доработки, добро пожаловать наПрограмма перевода самородковВы также можете получить соответствующие бонусные баллы за доработку перевода и PR. начало статьиПостоянная ссылка на эту статьюЭто ссылка MarkDown этой статьи на GitHub.

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из ИнтернетаНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории