Русский
Русский
English
Статистика
Реклама

Кодирование

Макраме из света шифрование данных на оптических узлах

21.10.2020 10:10:51 | Автор: admin


Научные изыскания позволяют нам не только лучше понимать окружающий наш мир, но и контролировать некоторые процессы и явления. За долгие годы исследований и экспериментов мы научились менять свойства материалов, манипулировать электромагнитными полями, видеть далекие планеты и звезды, разбирать по кирпичикам клетки и многое другое. Некоторые новообретенные умения сильно удивили бы ученых прошлого. Одним из таких умений является возможность менять форму луча света. Но как это применить на практике? Ученые из Оттавского университета (Оттава, США) предложили создать обрамленный оптический узел, который можно использовать для хранения и кодирования информации. Как ученые завязывали луч света в узел, каковы свойства такой структуры и насколько безопасно хранить данные на оптических узлах? На эти и другие вопросы мы найдем ответы в докладе ученых. Поехали.

Основа исследования


Любой моряк, дайвер или альпинист скажет, что правильный узел может спасти жизнь. Мастера макраме превратили узлы в настоящее искусство. А тайна наушников, самостоятельно запутывающихся в узлы, до сих пор остается не раскрыта.

Как мы прекрасно знаем, любой объект или процесс поддается математическому описанию, и узлы не исключение. С точки зрения математики, узел это вложение окружности в трехмерное евклидово пространство.


Типы простых узлов.

Математическая классификация узлов достаточно обширна (трилистник, печать Соломона, узел Листинга и т.д.). В данном же исследовании был задействован особый вид узлов обрамленный. Такой узел создается из плоской ленты. Грубо говоря, это своего рода запутанная лента Мебиуса.

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

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

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

Создание оптического обрамленного узла


Узел, как мы уже знаем, это описание того, как запутанные нити/линии/полосы расположены в пространстве. По этой причине при анализе в рамках физической структуры узлы обычно обнаруживаются в полях, определяемых областями, которые однозначно образуют кривые в трехмерном пространстве. Такие узловые кривые были продемонстрированы в таких системах, как вихри в жидкостях, нули интенсивности в скалярных оптических полях и в пределах C-линий оптических полей поляризации.

C-линии, в частности, состоят из кривых чистой круговой поляризации в монохроматических электромагнитных полях. Одна из их самых отличительных особенностей связана со структурой поляризационного поля в непосредственной близости от них. Если точнее, то они заключены в поляризационные эллипсы с большой осью, которая вращается на целые числа, кратные , вдоль замкнутого контура, окружающего C-линию ( и 1d).


Изображение 1

В случае параксиальных* оптических лучей поляризация ограничивается плоскостью, поперечной распространению луча, например плоскостью xy.
Параксиальный луч* луч, который распространяется вдоль оси центрированной оптической системы.
Как показано на , это ограничение уменьшает плоскость, в которой можно проследить вращение оси поляризации. Однако непараксиальные лучи могут иметь векторы поляризации, нормаль которых не перпендикулярна распространению луча. Как показано на 1b, этот нормальный вектор, в свою очередь, определяет плоскость, в которой ось эллипса совершает половину оборота вокруг C-линии.

Наличие этих вращений является ключевой структурной особенностью, рассматриваемой при определении исследуемых обрамленных узлов.

Обрамленный узел в трехмерном пространстве представляет собой узел, оснащенный векторным полем, называемым обрамлением. Обрамление нигде не касается узла и характеризуется коэффициентом зацепления. Другими словами, оно считает, сколько раз векторное поле поворачивается (на 2 поворотов) вокруг узла. Узловые ленты обобщают обрамленные узлы до нечетного числа полу-скручиваний, например, узловые ленты Мебиуса.

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

Данная концепция проиллюстрирована на и 1b, где разными цветами отмечены эллипсы поляризации, окружающие C-линию, ось которой перпендикулярна ее касательной, что и определяет ее обрамление.

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

На показано, что это можно реализовать посредством узлового поля Ek, определяемого циркулярно поляризованной составляющей (Ek-) с узловыми фазовыми сингулярностями и продольно поляризованной составляющей (Ekz), гарантирующей, что Ek соответствует уравнениям Максвелла.

Путем наложения Ek на плоскую волну с противоположной спиральностью поляризации (Ep+) создаются узловые C-линии, возникающие из сингулярной структуры Ek (1d и 1e).

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


Изображение 2

Например, узел трилистник () может быть выражен как закрытие косы на 2b. Такое представление можно применить и к узлам/косам в трехмерном пространстве. Например, трилистник, внедренный в тор (2c), может быть получен посредством стереографической проекции косы, заключенной в цилиндр (2d).

Один из способов выполнить эту проекцию выразить эту косу как нули комплексного поля. Это поле записывается как функция комплексных координат (u, v), которые относятся к пространственным координатам (x, y, h), в которые коса вложена через u = x + iy и v = exp(ih). Это заплетенное поле, в свою очередь, может быть преобразовано в соответствующий ему узел со стереографической проекцией, определяемой:



где (, , z) цилиндрические координаты трехмерного пространства, в которое теперь вложен узел.

Данная проекция превращает косу, определенную на (x, y, h), в узел в (, , z), соединяя два ее конца, тем самым отображая координату h на .

Вышеупомянутая проекция в значительной степени используется при построении узловых оптических полей. В частности, скалярное оптическое поле может быть построено путем согласования его поля вдоль плоскости z = 0 с полем комплексного узла, возникающего в результате проекции косы. Когда это оптическое поле является параксиальным, то его формулировка в последующих z-плоскостях может быть получена с помощью методов параксиального распространения. Затем этот метод может быть расширен для описания параксиальных узловых C-линий.

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

Также было использовано преобразование координат для кривой, образованной узловой С-линией. Это преобразование эффективно разрезает узел по заданному азимутальному углу и разворачивает его, тем самым сопоставляя координату узла с координатой h пространства. Во время этого процесса обеспечивается локальное сохранение ориентации обрамления узла. На показал узел трилистник до, а на 2f этот же узел после данной процедуры.

Такое преобразование позволило определить определенную информацию касательно узлов (угол закручивания, например). В данном случае угол закручивания состоит из азимутальной ориентации ленты в обрамлении, где нормаль совпадает с касательной к развернутому узлу (2g).

Кодирование информации на узел


Учитывая возможность извлечь угол закручивания из оптического обрамленного узла, появляется возможность использовать данную структуру для записи информации.

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



где k обозначает прядь в косе рассматриваемого обрамленного узла, dk количество полуоборотов вдоль k пряди, демонстрирующей полуоборот (т.е. dk = если пряди не скручены), pk простое число, присвоенное k пряди. M = kdk состоит из общего числа полуоборотов в обрамлении узла.

Вышеперечисленные переменные позволяют определить натуральное число:



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

Теоретический пример: Алиса и Боб


Далее ученые предлагают теоретический пример того, как этот процесс будет выглядеть. Предположим, что Алиса хотела бы отправить Бобу сообщение.

Это сообщение является результатом работы (выходные данные) программы, обрабатывающей некие входные данные (набор чисел dk, где k = 1, 2,, n). Ожидается, что запуск программы с таким набором предоставит сообщение Алисы.

Алиса представляет свою программу и ее выходные данные в виде обрамленной косы. Сама операция, выполняемая программой, идентифицируется как последовательность пересечений на планарной диаграмме косы, а исходные данные это количество полуоборотов на прядь. Программа Алисы полностью определена как обрамленная коса с n прядями в виде узловой ленты (КA).

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

Следовательно, необходимо выполнить ряд действий. Сначала нужно выбрать натуральное число . Далее определить проекцию обрамленной косы по отношению к КA. Для этого нужно распределить количество полуоборотов в КA для разных прядей косы, то есть установить dk так, чтобы MA = kdk.

Следом необходимо присвоить простые числа pk прядям, демонстрирующим полуобороты. И наконец определить число согласно формуле 2.

После того как данная процедура завершена, Алиса может отправить Бобу ленту КA, завязанную узлом, и числа (, ).

Естественно, полученное сообщение необходимо расшифровать. Для этого Боб должен вычислить N,(MA), разложение которых на простые множители дает dk. За счет этого Боб может восстановить оригинал обрамленной косы, которую отправила ему Алиса.


Изображение 3

Данная операция по обмену данными показана на схеме выше.

Если свести все к простым терминам, то у Алисы есть лента (данные), которая она хочет передать Бобу. Эту ленту можно преобразовать в сложный узел и закодировать исходное состояние, предоставив средства для декодирования исключительно Бобу.

Практические эксперименты



Изображение 4

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

Это устройство разделяет однородно поляризованный световой луч на две ортогонально поляризованные компоненты, каждая из которых модулируется пространственным модулятором света (SLM от spatial light modulator). SLM отображает голограммы, в которых зашифрованы как интенсивность, так и фаза целевого оптического поля.

Одна компонента модулируется для получения пучка с узловыми оптическими вихрями, такими как Ek- (1c). Вторая компонента модулируется, чтобы сформировать большой гауссов пучок, который равномерно покрывает всю узловую составляющую, тем самым эффективно принимая на себя роль плоской волны Ep+ (1c).

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

С помощью данной экспериментальной установки удается получить узлы разных типов: трилистник и печать Соломона (пятилистник). На 4b показаны голограммы, отображаемые на SLM, а также амплитуды и фазы полей, которые они должны создавать.

Фаза поля для узла трилистника и для узла пятилистника представлены следующими формулами:





где масштабированная и безразмерная версия цилиндрической радиальной координаты, азимутальная координата, a, b, s параметры, определяющие форму узла.

Для узла-трилистника рассматривались параметры a = 1, b = 0.5 и s = 1,2, тогда как для узла-пятилистника использовались a = 0.5, b = 0.24 и s = 0.65.


Изображение 5

Обрамленные узлы, полученные в ходе теоретических опытов, показаны на . А вот на 5b показаны узлы, полученные в ходе практических опытов. Помимо незначительных дефектов, возникающих в местах стыковки С-линий на концах узлов, наблюдается очень хорошее согласование теории и экспериментальных результатов. Схемы показывают развернутый вариант экспериментально полученных узлов. Сравнение числа полуоборотов также показало значительное совпадение теории и практики (5d).

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

Эпилог


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

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

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

Кроме того, данное исследование может помочь в топологических квантовых вычислениях, поскольку можно существенно снизить степень шума, который является одной из основных проблем в данной области. Конечно, это лишь теоретические предположения, которые еще предстоит проверить на практике. Тем не менее результатов, полученных в ходе данного исследования, уже достаточно, чтобы более оптимистично смотреть на грандиозные планы ученых.

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

Немного рекламы


Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
Подробнее..

Неоконченная история QR-кода

21.03.2021 20:19:46 | Автор: admin

Мы встречаемся с ними всюду: на водосточных трубах жилых массивов и поручнях метро. В рекламных роликах крупных брендов и сервисах регистрации. Даже в видеоигре Alan Wake QR-коды, простите за каламбур, засветились в качестве пасхалок с дополнительным контентом.

Чуть ли не ежегодно возникают убийцы QR-кодов, а им самим предрекают скорую гибель. Но уже не одно десятилетие люди продолжают пользоваться этими черно-белыми квадратиками. Зачем? Почему? Кто их придумал? Попробуем разобраться под катом.

Япония издавна славится разного рода изобретениями, призванными сделать бизнес-процессы и производственные задачи как можно более компактными и эффективными. В начале 1990-х годов перед инженерами крупной машиностроительной компании Denso стояла нетривиальная задача: создать унифицированный штрих-код (или нечто подобное) для маркировки деталей и компонентного сканирования. На тот момент внутри компании были приняты более 10 кодов разного назначения, и сотрудники завода жаловались на то, что работа с кодами требует большой концентрации, а сами коды содержат чрезвычайно мало полезной информации.

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

Китайские шашки и японская смекалка

Масахиро Хара, сотрудник отдела разработки Denso Wave, в 1992 году взялся за решение этой задачи. Новые коды должны были отвечать следующим требованиям:

  • объем информации, которую возможно хранить в коде, должен существенно возрасти;

  • процесс считывания должен быть как можно более точным и быстрым;

  • сами коды должны быть устойчивы к пятнам от масла, грязи и прочим повреждениям;

  • считывающее устройство должно быть простым и дешевым.

По легенде, вдохновение пришло к Масахиро за обедом, во время игры в го. Что ж, очень похоже на правду: QR-код действительно напоминает доску для игры с расставленными на ней камушками, а игровая ситуация это те же закодированные данные.

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

По словам Масахиро, квадратики, из которых состоит код, также были выбраны не случайно: выяснилось, что паттерны из квадратов практически не встречаются в бизнес-документах и в маркировке в целом. Таким образом, вероятность ошибки при считывании, вызванной паразитными данными, сводится к нулю. В целях дополнительной страховки Масахиро предложил использовать определенный размер отступов между информационной частью паттерна и его границами. Конечный формат кода определяется следующим соотношением габаритов черных и белых пикселей: 1:1:3:1:1. Считывающее устройство способно распознать код, расположенный под любым углом, ориентируясь лишь по этому соотношению.

К 1994 году новый формат кода (Quick Response Code) был повсеместно внедрен на заводах производственной цепочки автоконцерна Toyota, но быстро перетек из цехов в другие бизнес-сферы. Масахиро Хара вспоминает, что вплоть до презентации нового формата кода он не был уверен, что его детище приживется в компании. Да, скорость считывания данных и надежность формата не вызывали сомнений, однако 2D-сканеры могли стать серьезным препятствием на пути внедрения технологии. Тем не менее код был воспринят и главами, и рядовыми сотрудниками корпорации очень тепло. В течение следующего месяца удалось успешно внедрить его в собственную Kanban-программу Toyota.

Не секрет, что японцы любят свои изобретения и не выпустят любимую игрушку из рук, пока не появится её более технологичный наследник. То же произошло с QR-кодами: с 2002-2003 года их стали применять в ресторанах для маркировки контейнеров, в делопроизводстве. Известны также случаи применения QR-кодов в школах, музеях и на кладбищах.

QR-коды захватывают мир

Простота и удобство кода понравились людям и за пределами Японии. К середине-концу 2000-х годов о японском изобретении узнал весь мир. При этом фраза-обозначение QR code является зарегистрированным товарным знаком, принадлежащим компании-изобретателю, однако использование самих кодов не облагается отчислениями.

Говорить о версиях QR-кодов можно достаточно долго: существуют и маленькие версии (21х21px), и более крупные 177х177px. Вот основные принятые во всем мире кодировки данных:

  • цифровая кодировка, до 7089 цифр;

  • алфавитно-цифровая кодировка, до 4296 символов (или до 2953 символов с поддержкой кириллицы);

  • байтовая кодировка, до 2953 байт;

  • кодировка кандзи, до 1817 иероглифов.

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

Опустим технические моменты, лежащие в основе принципа QR-кода: этой информации и на Хабре, и за его пределами предостаточно. Гораздо интереснее сконцентрироваться на том, как эти коды используются вне рамок бизнес-задач.

Примечание: QR-коды ниже представлены исключительно для демонстрации технологии. Автор статьи не несет ответственности за их содержание сканируйте на свой страх и риск :)

Двумерный креатив

Игра с цветом

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

Игра с формой

Закругленные QR-коды, коды, в которые вписаны изображения и логотипы также не новость. Чтобы устройства могли разобрать нестандартные с точки зрения формы коды, применяется технология избыточного кодирования.

Особняком здесь стоят дизайнерские варианты QR-кодов: это не просто вписывание квадратика с изображением в поле кода, это целое произведение искусства. Ну, почти искусства.

Коды с нестандартной ориентацией в пространстве также не новы.

Кроме того, периодически можно встретить анимированые QR-коды, однако это, скорее, модная диковинка, нежели оправданное использование технологии.

Рукотворные QR-коды: благодаря общей простоте кода, его легко можно воссоздать не только на бумаге, но и с помощью подручных средств.

Игры с применением

Открытки, футболки, бижутерия с памятными шифровками даже сюда добрались QR-коды.

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

Ритейл не остался в стороне: в QR-кодах шифруются коды скидочных купонов и номера карт для программ лояльности. Впрочем, здесь у QR-кода есть сильные конкуренты, например, NFC-решения.

QR-коды все еще популярны среди рекламодателей: в кодах шифруются адреса сайтов и ссылки на скачивание приложений своеобразная попытка перевести пользователей из оффлайна в онлайн.

Сомнительное решение наручные часы, которые показывают время в зашифрованном варианте.

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

Японская виза здесь без комментариев. :)

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

Татуировки опять же, без комментариев. Главное, чтобы мастер ничего не напутал. Агент 47 шлет пламенный привет.

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

Проект бизнес-центра в ОАЭПроект бизнес-центра в ОАЭ

Киса и Ося были тут: QR-коды используются также в так называемой психогеографии. Люди записывают свои мысли, ассоциации и воспоминания, связанные с разными местами, и распространяют их в виде QR-кодов.

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

Игры с содержанием

Пароли от гостиничного Wi-Fi, географические координаты, ссылки на меню это весьма традиционные варианты использования кода. Как насчет чего-то более интересного?

Сервис QRInfoPoint предлагает достаточно забавное решение для передачи музыки, фото или видео через QR-код. Задумка проста и элегантна: разумеется, вместить целый аудио-файл в код не получится, однако вполне возможно залить его на сервер (или воспользоваться уже существующей ссылкой, например, на YouTube), а в код интегрировать адрес html-странички с соответствующим тегом и атрибутом src, по которому будет загружена и проиграна композиция.

Симпатичные QR-коды использует Nintendo в играх серии Pokemon (и некоторых других) для передачи информации, обмена покемонами и многого другого.

Совершенно сумасшедший, но работающий QR-код. Опять же, в стилистике Nintendo.

Попытка зашифровать в QR-коде целую игру:

Убийцы и прочие родственники QR-кода

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

Приложение PhonoPaper позволяет зашифровать аудио до 10 секунд в изображении или произвести расшифровку.

Приложение Честный знак для проверки подлинности товаров и получения дополнительной информации по различным кодам.

Кроме того, с успехом выполняют задачи, возложенные маркетологами и любителями фана на QR, технологии дополненной реальности, NFC и биконы.

Clickable paper проект, нацеленный на получение дополнительной информации из печатных материалов.

Убийца QR-кодов SnapTag обведи логотип кружком, и дело в шляпе.

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

Подробнее..

Снежная слепота беспилотных авто

02.06.2021 10:16:01 | Автор: admin


У природы нет плохой погоды, каждая погода благодать. Слова этой лирической песни можно понимать образно, интерпретировав погоду как отношения между людьми. Можно понимать и буквально, что также верно, ибо не было бы снежной и холодной зимы, мы бы не так ценили лето, и наоборот. Но беспилотные автомобили лишены лирических чувств и поэтического мироощущения, для них далеко не вся погода благодать, особенно зимняя. Одной из основных проблем, с которыми сталкиваются разработчики робомобилей, это снижение точности датчиков, указывающих машине куда ей ехать, во время плохих погодных условий. Ученые из Мичиганского технологического университета создали базу данных погодных условий на дорогах глазами беспилотных авто. Эти данные были нужны дабы понять что нужно изменить или улучшить, чтобы зрение робомобилей во время снежной бури было не хуже, чем в ясный летний день. Насколько плохая погода влияет на датчики беспилотных авто, какой метод решения проблемы предлагают ученые, и насколько он эффективен? Ответы на эти вопросы мы найдем в докладе ученых. Поехали.

Основа исследования


Работу беспилотных авто можно сравнить с уравнением, в котором очень много переменных, которые нужно учесть все без исключения для получения верного результата. Пешеходы, другие авто, качество дорожного покрытия (видимость разделительных полос), целостность систем самого беспилотника и т.д. Многие исследования ученых, провокационные заявления политиков, колкие статьи журналистов базируются на связи между беспилотным автомобилем (далее просто авто или автомобиль) и пешеходом. Это вполне логично, ибо человек и его безопасность должны стоять на первом месте, особенно учитывая непредсказуемость его поведения. Морально-этические споры о том, кто будет виноват, если автомобиль собьет пешехода, выскочившего на дорогу, продолжаются до сих пор.

Однако, если убрать из нашего образного уравнения переменную пешеход, то все равно останется много потенциально опасных факторов. Погода является одним из них. Очевидно, что в плохую погоду (ливень или снежная буря) видимость может снизиться настолько, что порой приходится просто остановиться, ибо ехать нереально. Зрение автомобилей, конечно, сложно сравнить со зрением человека, но их датчики страдают от снижения видимости не меньше нас. С другой стороны у машин есть более широкий арсенал этих датчиков: камеры, радары диапазона миллиметровых волн (MMW), система глобального позиционирования (GPS), гиростабилизатор (IMU), система обнаружение и определение дальности с помощью света (LIDAR) и даже ультразвуковые системы. Несмотря на это многообразие органов чувств, автономные машины все еще слепы во время плохой погоды.

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

При семантической сегментации вместо обнаружения объекта на изображении каждый пиксель классифицируется индивидуально и присваивается классу, который пиксель представляет лучше всего. Другими словами, семантическая сегментация это классификация на уровне пикселей. Классическая семантическая сегментация сверточная нейронная сеть (CNN от convolutional neural network) состоит из кодирующей и декодирующей сетей.

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

Двумя ключевыми компонентами в декодирующих сетях являются так называемые слой MaxUnpooling и слой свертки Transpose. Слой MaxUnpooling (аналог слоя MaxPooling операция пулинга с функцией максимума) необходим для снижения размерности обрабатываемых данных.


Пример операции MaxPooling.

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

Другой подход разместить значения в заранее определенном месте (например, в верхнем левом углу) в области, на которую указывает ядро. Именно этот метод и был использован в моделировании, речь о котором пойдет немного позже.

Транспонированный сверточный слой противоположен обычному сверточному слою. Он состоит из движущегося ядра, которое сканирует входные данные и свертывает значения для заполнения выходного изображения. Объемом вывода обоих слоев, MaxUnpooling и транспонированного можно управлять, регулируя размер ядра, отступы и шаг.

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

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

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

Третий, но не менее важный, аспект это объединение датчиков. Под этим подразумевается буквальное объединение данных от нескольких датчиков для получения более полной картины и уменьшения вероятных погрешностей и неточностей в данных отдельных датчиков. Существует однородное и неоднородное объединение датчиков. Примером первого может быть использование нескольких спутников для уточнения местоположения по GPS. Примером второго является объединение данных камер, LiDAR и Radar для беспилотных авто.

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


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

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

Сбор данных


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

Для проведения дальнейших работ, включающих расчеты, моделирование и тестирование, необходимо было много данных. Чем больше, тем лучше, говорят сами ученые, и это вполне логично, когда речь идет о работе различных датчиков (камеры, LiDAR и Radar). Среди множества уже существующих наборов данных был выбран DENSE, которые охватывает большую часть необходимых для исследования нюансов.

DENSE также является проектом, нацеленным на решение проблем нахождения пути в суровых погодных условиях. Ученые, работавшие над DENSE, проехали порядка 10000 км по Северной Европе, записывая данные с нескольких камер, нескольких LiDAR, радаров, GPS, IMU, датчиков дорожного трения и тепловизионных камер. Набор полученных данных состоит из 12000 выборок, которые можно разбить на более мелкие подгруппы, описывающие конкретные условия: день+снег, ночь+туман, день+ясно и т.д.

Однако для правильной работы модели необходимо было провести коррекцию данных из DENSE. Исходные изображения камеры в наборе данных имеют размер 1920 х 1024 пикселей, их уменьшили до 480 х 256 для более быстрого обучения и тестирования модели.

Данные LiDAR хранятся в формате массива NumPy, который нужно было преобразовать в изображения, масштабировать (до 480 x 256) и нормализовать.

Данные радара хранятся в файлах JSON, по одному файлу для каждого кадра. Каждый файл содержит словарь обнаруженных объектов и несколько значений для каждого объекта, включая x-координаты, y-координаты, расстояние, скорость и т.д. Такая система координат параллельна плоскости автомобиля. Чтобы преобразовать ее в вертикальную плоскость, нужно учитывать только y-координату.


Изображение 1: проецирование y-координаты на плоскость изображения (слева) и обработанный кадр радара (справа).

Полученные изображения подвергались масштабированию (до 480 x 256) и нормализации.

Разработка CNN модели



Изображение 2: архитектура разработанной CNN модели.

Сеть была спроектирована так, чтобы быть как можно более компактной, так как глубокие сети кодирования-декодирования требуют немало вычислительных ресурсов. По этой причине сеть декодирования не была спроектирована с таким количеством уровней, как сеть кодирования. Сеть кодирования состоит из трех потоков: камера, LiDAR и радар.

Поскольку изображения с камеры содержат больше информации, поток камеры сделан глубже, чем два других. Он состоит из четырех блоков, каждый из которых состоит из двух сверточных слоев слоя пакетной нормализации и слоя ReLU, за которым следует слой MaxPooling.

Данные LiDAR не столь массивны, как данные от камер, потому его поток состоит из трех блоков. Точно так же поток Radar меньше, чем поток LiDAR, потому состоит всего из двух блоков.

Выходные данные от всех потоков изменяются и объединяются в одномерный вектор, который подключен к сети из трех скрытых слоев с ReLU активацией. Затем данные преобразуются в двумерный массив, который передается в сеть декодирования, состоящую из четырех последовательных этапов MaxUnpooling и транспонированной свертки для повышения дискретизации данных до размера ввода (480x256).

Результаты обучения/тестирования CNN модели


Обучение и тестирование проводились на Google Colab с использованием GPU. Подмножество данных, размеченных вручную, состояло из 1000 выборок данных камеры, LiDAR и радара 800 для обучения и 200 для тестирования.


Изображение 3: потери в обучающих выборках во время фазы обучения.

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


Изображение 4: точность в тестовых выборках во время фазы тестирования.

Ученые отмечают, что самым простым показателем точности системы является пиксельная, т.е. отношение правильно определенных пикселей и неправильно определенных пикселей к размеру изображения. Пиксельная точность рассчитывалась для каждой выборки в наборе тестирования, среднее из этих значений и представляет общую точность модели.

Однако этот показатель не является идеальным. В некоторых случаях определенный класс недостаточно представлен в выборке, от чего точность пикселей будет значительно выше (чем на самом деле) из-за того, что не хватает пикселей для тестирования модели для определенного класса. Посему было решено дополнительно использовать MIoU среднее отношение области пересечения к области объединения.


Визуально представление IoU.

Подобно точности пикселей, точность по IoU вычисляется для каждого кадра, а конечный показатель точности это среднее от этих значений. Однако MIoU рассчитывается для каждого класса отдельно.


Таблица значений точности.


Изображение 5

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

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

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

Эпилог


Отношение к беспилотным автомобилям неоднозначное. С одной стороны, робомобиль нивелирует такие риски, как человеческий фактор: нетрезвый водитель, лихачество, безответственное отношение к ПДД, малый опыт вождения и т.д. Другими словами, робот не ведет себя как человек. Это хорошо, так ведь? И да, и нет. Во многом автономные транспортные средства превосходят водителей из плоти и крови, но далеко не во всем. Плохая погода тому яркий пример. Человеку, конечно, непросто ехать во время снежной бури, но для беспилотных авто это было практически нереально.

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

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

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

Немного рекламы


Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Maincubes Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
Подробнее..

Кодирование для чайников, ч.1

01.01.2021 18:11:05 | Автор: admin

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

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

0. Начало

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

Чего мне не хватало в 70-80-е, так это в школе, пусть не на информатике, а, например, на уроках математики - базовой информации по кодированию. Дело в том, что кодированием информации каждый из нас занимается ежесекундно, постоянно и в целом - не концентрируясь на самом кодировании. То есть в быту мы это делаем постоянно. Так как это происходит?

Мимика, жесты, речь, сигналы разного уровня - табличка с надписью, знак на дороге, светофоры, и для современного мира - штрих- и бар-коды, URL, хэш-тэги.

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

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

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

1.2 Чередующиеся сигналы

Индеец пингуетИндеец пингует

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы "включено/выключено". Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме "точка-тире", что нам даёт букву "A" может звучать и так - "точка-пауза-тире" и тогда это уже две буквы "ET".

1.3 Контекст

Когда мы пользуемся компьютером, мы понимаем, что информация бывает разной - звук, видео, текст. Но в чем основные различия? И до того, как начать информацию кодировать, чтобы, например, передавать её по каналам связи, нужно понять, что из себя представляет информация в каждом конкретном случае, то есть обратить внимание на содержание. Звук - череда дискретных значений о звуковом сигнале, видео - череда кадров изображений, текст - череда символов текста. Если мы не будем учитывать контекст, а, например, будем использовать азбуку Морзе для передачи всех трёх видов информации, то если для текста такой способ может оказаться приемлемым, то для звука и видео время, затраченное на передачу например 1 секунды информации, может оказаться слишком долгим - час или даже пара недель.

2. Кодирование текста

От общего описания кодирования перейдём к практической части. Из условностей вы за константу примем то, что будем кодировать данные для персонального компьютера где за единицу информации приняты - бит и байт. Бит, как атом информации, а байт - как условный блок размером в 8 бит.

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт в значении ноль равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Символ

Количество

ПРОБЕЛ

18

Р

12

К

11

Е

11

У

9

А

8

Г

4

В

3

Ч

2

Л

2

И

2

З

2

Д

1

Х

1

С

1

Т

1

Ц

1

Н

1

П

1

Всего нами использовано 19 символов (включая пробел). Для хранения в памяти ПК будет затрачено 18+12+11+11+9+8+4+3+2+2+2+2+1+1+1+1+1+1+1=91 байт (91*8=728 бит).

Эти значения мы берём как константы и пробуем изменить подход к хранению блоков. Для этого мы замечаем, что из 256 кодов для символов мы используем только 19. Чтобы узнать - сколько нужно бит для хранения 19 значений мы должны посчитать LOG2(19)=4.25, так как дробное значение бита мы использовать не можем, то мы должны округлить до 5, что нам даёт максимально 32 разных значения (если бы мы захотели использовать 4 бита, то это дало бы лишь 16 значений и мы не смогли бы закодировать всю строку).

Нетрудно посчитать, что у нас получится 91*5=455 бит, то есть зная контекст и изменив способ хранения мы смогли уменьшить использование памяти ПК на 37.5%.

К сожалению такое представление информации не позволит его однозначно декодировать без хранения информации о символах и новых кодах, а добавление нового словаря увеличит размер данных. Поэтому подобные способы кодирования проявляют себя на бОльших объемах данных.

Кроме того, для хранения 19 значений мы использовали количество бит для 32 значений, это снижает эффективность кодирования.

2.2 Коды переменной длины

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

Символ

Количество

Переменный код, бит

ПРОБЕЛ

18

0

Р

12

1

К

11

00

Е

11

01

У

9

10

А

8

11

Г

4

000

В

3

001

Ч

2

010

Л

2

011

И

2

100

З

2

101

Д

1

110

Х

1

111

С

1

0000

Т

1

0001

Ц

1

0010

Н

1

0011

П

1

0100

Для подсчёта длины закодированного сообщения мы должны сложить все произведения количества символов на длины кодов в битах и тогда получим 179 бит.

Но такой способ, хоть и позволил прилично сэкономить память, но не будет работать, потому что невозможно его раскодировать. Мы не сможем определить в такой ситуации что означает код "111", это может быть "РРР", "РА", "АР" или "Х".

2.3 Префиксные блочные коды

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

Составим третью таблицу всё для той же строки:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

0000

Р

12

0001

К

11

0010

Е

11

0011

У

9

0100

А

8

0101

Г

4

0110

В

3

0111

Ч

2

10001

Л

2

10010

И

2

10011

З

2

10100

Д

1

10101

Х

1

10110

С

1

10111

Т

1

11000

Ц

1

11001

Н

1

11010

П

1

11011

Особенность новых кодов в том, что первый бит мы используем для указания размера следующего за ним блока, где 0 - бок три бита, 1 - блок четыре бита. Нетрудно посчитать, что такой подход закодирует нашу строку в 379 бит. Ранее при блочном кодировании у нас получился результат в 455 бит.

Можно развить этот подход и префикс увеличить до 2 бит, что позволит нам создать 4 группы блоков:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

000

Р

12

001

К

11

0100

Е

11

0101

У

9

0110

А

8

0111

Г

4

10000

В

3

10001

Ч

2

10010

Л

2

10011

И

2

10100

З

2

10101

Д

1

10110

Х

1

10111

С

1

11000

Т

1

11001

Ц

1

11010

Н

1

11011

П

1

11100

Где 00 - блок в 1 бит, 01 - 2 бита, 10 и 11 - 3 бита. Подсчитываем размер строки - 356 бит.

В итоге за три модификации одного способа мы регулярно уменьшаем размер строки, от 455 до 379, а затем до 356 бит.

2.4 Код Хаффмана

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

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

Символ

Количество

Код

ПРОБЕЛ

18

00

Р

12

101

К

11

100

Е

11

011

У

9

010

А

8

1111

Г

4

11011

В

3

11001

Ч

2

111011

Л

2

111010

И

2

111001

З

2

111000

Д

1

1101011

Х

1

1101010

С

1

1101001

Т

1

1101000

Ц

1

1100011

Н

1

1100010

П

1

110000

Считаем результат - 328 бит.

Заметьте, хоть мы и стали использовать коды в 6 и 7 бит, но их слишком мало, чтобы повлиять на исход.

2.5.1 Строки и подстроки

До сих пор мы кодировали данные, рассматривая их как совокупность отдельных символов. Сейчас мы попробуем кодировать целыми словами.

Напомню нашу строку: "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

Составим таблицу повторов слов:

Слово

Количество

ПРОБЕЛ

18

ГРЕКА

3

В

2

РАК

2

РЕКУ

2

РУКУ

2

ВИДИТ

1

ГРЕКУ

1

ЕХАЛ

1

ЗА

1

РЕЧКЕ

1

СУНУЛ

1

ЦАП

1

ЧЕРЕЗ

1

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

Сначала формируем словарь:

Слово

Количество

Индекс

ГРЕКА

3

0

В

2

1

РАК

2

2

РЕКУ

2

3

РУКУ

2

4

ВИДИТ

1

5

ГРЕКУ

1

6

ЕХАЛ

1

7

ЗА

1

8

РЕЧКЕ

1

9

СУНУЛ

1

10

ЦАП

1

11

ЧЕРЕЗ

1

12

Таким образом наша строка кодируется в последовательность:

7, 0, 12, 3, 5, 0, 1, 9, 2, 10, 0, 4, 1, 3, 2, 8, 4, 6, 11

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

Индексы записываем в виде блоков по 4 бита (так можно представить индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для соответствия индексу и слову. Сами слова будем кодировать кодами Хаффмана, только нам еще придется задать разделитесь записей в словаре, можно, например, указывать длину слова блоком, самое длинное слово у нас в 5 символов, для этого хватит 3 бита, но так же мы можем использовать код пробела, который состоит из двух бит - так и поступим. В итоге мы получаем схему хранения словаря:

Индекс / биты

Слово / биты

Конец слова / биты

0 / 4

ГРЕКА / 18

ПРОБЕЛ / 2

1 / 4

В / 5

ПРОБЕЛ / 2

2 / 4

РАК / 10

ПРОБЕЛ / 2

3 / 4

РЕКУ / 12

ПРОБЕЛ / 2

4 / 4

РУКУ / 12

ПРОБЕЛ / 2

5 / 4

ВИДИТ / 31

ПРОБЕЛ / 2

6 / 4

ГРЕКУ / 17

ПРОБЕЛ / 2

7 / 4

ЕХАЛ / 20

ПРОБЕЛ / 2

8 / 4

ЗА / 10

ПРОБЕЛ / 2

9 / 4

РЕЧКЕ / 18

ПРОБЕЛ / 2

10 / 4

СУНУЛ / 26

ПРОБЕЛ / 2

11 / 4

ЦАП / 17

ПРОБЕЛ / 2

12 / 4

ЧЕРЕЗ / 21

ПРОБЕЛ / 2

7

0

12

3

5

0

1

9

2

10

0

4

1

3

2

8

4

6

11

и само сообщение по 4 бита на код.

Считаем всё вместе и получаем 371 бит. При этом само сообщение у нас было закодировано в 19*4=76 бит. Но нам всё еще требуется сохранять соответствие кода Хаффмана и символа, как и во всех предыдущих случаях.

Послесловие

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

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

Подробнее..

Кодирование и Шифрование

22.03.2021 14:08:01 | Автор: admin

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

Но зачем это вообще нужно знать? Чтобы попросту не попасть в ситуацию, когда ваши личные данные, пароли от аккаунтов или банковских карт окажутся в руках мошенников. Как говорится: Доверяй, но проверяй

Важные аспекты в хранении данных, будь то на внешних серверах или домашнем компьютере, это прежде всего кодирования и шифрование. Но чем они отличаются друг от друга? Давайте разбираться!

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

Определения и различия

Кодирование процесс преобразования доступной нам информации в информацию понятную компьютерную.

Шифрование процесс изменения информации таким образом, чтобы её смогли получить только нужные пользователи.

Шифрование применялось и задолго до создания компьютеров и информатики как таковой. Но зачем? Цели её применения можно было понять из определения, но я опишу их ещё раз более подробно. Главные цели шифрования это:

  • конфиденциальность данные скрыты от посторонних

  • целостность предотвращение изменения информации

  • идентифицируемость возможность определить отправителя данных и невозможность их отправки без отправителя

Оценить стойкость шифра можно с помощью криптографической стойкости.

Криптографическая стойкость это свойство шифра противостоять криптоанализу, изучению и дешифровки шифра.

Криптостойкость шифра делится на две основные системы: абсолютно стойкие системы и достаточно стойкие системы.

Абсолютно стойкие системы системы не подверженные криптоанализу. Основные критерии абсолютно стойких систем:

  • Ключи должны генерироваться для каждого сообщения отдельно

  • Генерация ключей независима

  • Длинна ключа должна быть не меньше длинны сообщения

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

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

  • Количества перехваченных сообщений

  • Времени и вычислительных способностей

А также от вычислительной сложности шифра.

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

История шифрования

Шифрование берет своё начало ещё из древних времен. Примерно 1300 лет до нашей эры был создан один из первых методов шифрования Атбаш. Принцип шифрования заключается в простой подставке символов по формуле:n-i+1, где:

  • n количество символов в алфавите

  • i порядковый номер символа.

Шифр получил своё название в честь первой, последней, второй и предпоследней буквы Еврейского алфавита - алеф, тав, бет, шин. Такой шифр имеет низку криптографическую стойкость, потому как алгоритм шифрования довольно прост

С тех самых пор шифрование активно развивалось вместе с развитием нашей цивилизации

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

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

К слову: Простые числа это те числа, которые могут делиться без остатка либо на 1, либо на себя.

Длинна таких чисел может быть абсолютно любая. К примеру, возьмем два простых числа 223 и 13. Их произведение 2899 будет являться открытым ключом, который мы и будем передавать по открытому каналу связи. Далее нам необходимо вычислить функцию Эйлера для произведения этих чисел.

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

Возможно, звучит непонятно, но давайте это разберем на небольшом примере:

(26) [фи от двадцати шести] = какому-то числу чисел, которое всегда будет меньше 26, а сами числа должны иметь только один общий делитель единицу с 26.

Давайте считать:

1 подходит всегда, идем дальше;

2 делится и на 2, и на 1, как и число 26, - не подходит;

3 делится и на 3, и на 1, а вот число 26 не делится на 3, - подходит;

4 имеет общие делители 2 и 1 с 26 - не подходит;

5 только на 1 - подходит;

6 на 2 и 1 - не подходит;

7 только на 1 подходит;

и так далее до 25.

Общее количество таких чисел будет равно 12. А найти это число можно по формуле: (n*k) = (n-1)(k-1) в нашем случае 26 можно представить как 2 * 13, тогда получим (26) = (2 * 130) = (2-1)*(13-1) = 1 * 12 = 12

Теперь, когда мы знаем, что такое функция Эйлера и умеем её вычислять найдем её для нашего открытого ключа (2899) = (223 * 13) =(223 1)*(13-1) = 222 * 12 = 2664

После чего нам нужно найти открытую экспоненту. Не пугайтесь, тут будет гораздо проще чем с функцией Эйлера.

Открытая экспонента это любое простое число, которое не делится на функцию Эйлера. Для примера возьмем 13. 13 не делится нацело на число 2664. Вообще открытую экспоненту лучше выбирать по возрастанию простым перебором, а не просто брать случайную. Так для нашего примера разумнее было бы взять число 5, но давайте рассмотрим на примере 13

Следующий шаг закрытая экспонента. Вычисляется она банальным перебором по этому равенству: d * e mod (n) = 1, где

  • (n) - функция Эйлера

  • e открытая экспонента

  • mod остаток отделения

а число d, которое и является закрытой экспонентой, мы должны подобрать перебором, либо попытаться выразить через формулу d = ceil((n) / e), где ceil округление в большую сторону.

В обоих случаях у нас получится число 205

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

Теперь этому человеку нужно отправить нам сообщение, для простоты предположим, что это какое-то число, например: 92. Для этого ему нужно отправить нам остаток от деления 92 в степени открытой экспоненты на открытый ключ T ^ e mod n, где

  • T шифруемый текст

  • e открытая экспонента

  • n открытый ключ

  • mod остаток от деления

92 ^ 13 mod 2899 = 235. Именно число 235 он нам и отправит.

Предположим, что и в этот раз сообщение перехватили, но нам оно всё так же дошло

Для расшифровки сообщения нам необходимо зашифрованное сообщение возвести в степень закрытой экспонентой и вычислить остаток от деления на открытый ключ C ^ d mod n, где

  • С зашифрованный текст

  • d закрытая экспонента

  • n открытый ключ

  • mod остаток от деления

235 ^ 205 mod 2899 = 92.

Вуаля, и мы имеет исходное число. Но, что насчет перехваченных сообщений? У злоумышленника есть сообщение, ключ и экспонента, но как мы помни для дешифровки ему ещё нужна секретная экспонента, она же секретный ключ, но для того, чтобы вычислить её, ему придется разложить исходный ключ 2899 на множители, а сделать это не так уж и просто, особенно когда вместо двух чисел 223 и 13, будут использовать числа длинной несколько десятков символов

Но ничто в мире не идеально, в том числе и этот метод.

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

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

Третий недостаток подбор и перебор чисел для экспонент.

Четвертый длинна ключей. Чем больше длинна, тем медленнее идет процесс декодирования, поэтому разработчики пытаются использовать наименьшие по длиннее ключи и экспоненты. Даже я акцентировал на это внимание, когда говорил, что лучше взять число 5, вместо 13 для открытой экспоненты. Именно из-за этого и происходит большая часть взломов и утечек данных

Но не стоит печалиться, ведь как я и говорил: криптография и шифрование развивается вместе с развитием цивилизации. Поэтому довольно скоро все мы будем шифровать свои данные с помощью Квантового шифрование.

Этот метод основывается на принципе квантовой суперпозиции элементарная частица может сразу находится в нескольких положениях, иметь разную энергию или разное направление вращения одновременно. По такому принципу и работает передача ключей шифрования по протоколу BB-84.

Есть оптоволокно, по которому передаются единичные фотоны света. Мы, как отправитель может сгенерировать абсолютно любой двоичный ключ, по тому же принципу квантовой супер позиции, ну или использовать обычные генераторы псевдослучайных чисел. Допустим мы хотим передать ключ 101001011. Для этого нам нужно принять за обозначение какое положение фотона соответствует единице, а какое нулю. Представим, что вертикальное положение это 1, а горизонтальное 0. Если оставить все так, то от передачи ключей таким образом не будет никакого смысла, ведь тогда злоумышленник всегда сможет измерить фотон, получить его значение, создать и отправить точно такой же обратно человеку, которому мы хоти передать ключ. Поэтому были введены ещё два положение диагональные. Предоставим вертикальную волну, или же значение 1 и отклоним её на 45 градусов влево. Это будет вторая единица. Вернемся обратно и отклоним на 45 градусов вправо это будет второй 0.

Вернемся к нашему ключу 101001011. Мы случайным образом выбираем направление обычное или диагональное. Для удобства присвоим обычному номер 1, а диагональному 2.

Давайте отправим ключ 1(1), 0(2), 1(1), 0(1), 0(1), 1(2), 0(2), 1(1), 1(2). Теперь человеку, которому мы отправляем ключ, нужно точно так же, совершенно случайно, выбрать случайное направление.

Допустим он выбрал направления: 221111212. Поскольку есть всего 2 плоскости отправки: 1 и 2, они же называются: канонический и диагональный базис, то шанс того, что он выбрал правильные направления 50%.

Если он угадал базис он получил верное значение, если нет неверное. Учитывая его направления, он получил: 001000011. Теперь нужно отсеять неправильные значения: можно сделать это обменом базисов по любому, даже не защищенному, каналу связи. После этого у нас обоих останется ключ: 0100011. Теперь с помощью его мы можем передавать и кодировать сообщения по обычному методу шифрования.

А что, если кто-то перехватит отправку кода? Тогда ему придется точно также подбирать случайным образом базисы, что добавит ещё 25% погрешности при получении кода человеку, которому мы изначально и отправили его. Чтобы проверить это, после отсеивания мы, как отправитель, должны проверить сколько процентов кода оказалось не верным. В нашем 1 случае это (9 7)/9 * 100% = 22%, если это число будет больше 50%, то мы начнем повторную отправку ключей, до тех пор, пока погрешность не будет меньше 50%

Заключение

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

Список литературы и материалов:

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru