Sdr

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

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

• Интернет вещей по-русски. Минимализм и открытость OpenUNB
• Интернет вещей по-русски. Многоканальная мощь физуровня базовой станции OpenUNB
• Интернет вещей по-русски. Помехоустойчивое кодирование в OpenUNB

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

Канальный уровень отвечает за механизм управления доступом устройств к радиоканалу (Media Access Control, MAC) и механизм управления логической связью (Logical Link Control, LLC) между устройствами и сервером сети.

Канальный уровень определяет:

1. механизм множественного доступа устройств к радиоканалу;
2. механизм повторных передач пакетов;
3. формат пакетов канального уровня и алгоритм их формирования;
4. схему адресации устройств;
5. процедуру активации (аутентификации и регистрации) устройств на сервере;
6. механизм криптографической защиты передаваемых данных (шифрование, контроль целостности и подлинности).

Сегодня мы рассмотрим первые четыре пункта списка.

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

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

Формат пакета OpenUNB по уровням:

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

В эти шесть байт входят адрес (DevAddr) и проверочное слово (MIC). Обе эти части имеют одинаковый размер (три байта) и простые, но тщательно отточенные разработчиками свойства.

Слово DevAddr это временный адрес устройства. В лирическом отступлении можно отметить, что мало можно найти протоколов IoT, в которые внедрена концепция временных адресов, хотя в сотовой связи она присутствует начиная со стандартов 2G. В OpenUNB временный адрес (меняется каждые 4 часа) формируется криптографически из базового ключа K0, привязанного к DevID, назначение которого имеет необыкновенную гибкость. Во-первых, DevID может не быть уникальным. Пользователь даже может назначить DevID случайным образом. Уникальность DevID придаст назначение соответствующего ему базового секретного ключа K0. Во-вторых, нет даже требований к длине DevID. Стандарт требует иметь его длину не менее 4 байт, но рекомендует длину 16 байт. В-третьих, такая гибкость приводит к возможности назначать DevID в разных сетях децентрализовано, не сверяясь друг с другом.

Если говорить точно, временный адрес DevAddr вырабатывается так:

где Ne номер эпохи (время), а Ka ключ активации, который получается так:

где Na номер активации, а K0 базовый секретный ключ.

Процедуры ECB и CTR здесь это криптопреобразования "режим простой замены" и "режим гаммирования", соответственно. Эти процедуры определены в стандартах шифрования ГОСТ.

Таким образом, если считать криптопреобразования стойкими, а ключ K0 секретным, связь между DevID и DevAddr экономически оправданным способом установить не получится. Поэтому третья сторона не может сопоставить пакеты в эфире с конкретным устройством IoT, не зная ключ K0. Какой еще протокол IoT может похвастаться таким удивительным свойством?!

Слово MIC, проверочное слово, уникально. Оно имеет по меньшей мере две ипостаси: это имитовставка и слово контроля целостности в одном лице. За счет этого двойного назначения получается немалая экономия в объеме данных, а значит и в энергии, потребляемой устройством. Есть еще третья функция MIC, скрытая от неискушенного читателя. Это конкретизация соответствия DevAddr и DevID. Очевидно, ввиду малости длины DevAddr, это поле не будет уникальным для всех DevID, по крайней мере это не гарантируется криптопреобразованиями. Но существует связь DevAddr и MIC, которая определяется секретным ключом K0 и другими параметрами. Если говорить точно, то чудо-слово MIC получается так:

где значение вектора P зависит от длины блока n и длины поля MACPayload. Пусть len
однобайтная целочисленная беззнаковая переменная, равная длине полезных данных
MACPayload в битах (переменная len может принимать значения 16 или 48), тогда:

если len = 48 и n = 64, то

в остальных случаях

Процедура CMAC24 здесь это криптопреобразование "режим выработки имитовставки" согласно ГОСТ.

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

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

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

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

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

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

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

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

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

В OpenUNB активация устройства производится пользователем. Также необходим доверенный канал между пользователем и сервером сети. Схема взаимодействия представлена ниже:

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

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

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

Рассмотрим подробно процедуру со стороны устройства и со стороны сервера.

Со стороны устройства процедура выглядит так:

1. проверяется текущее значение счетчика активаций Na. Если счетчик активаций уже достиг максимально возможного значения, то данное устройство больше не может использоваться, и выключается;
2. увеличивается значение счетчика активаций: Na = Na + 1;
3. вырабатывается ключ активации Ka;
4. вырабатывается ключ расчета имитовставки Km для эпохи Ne = 0;
5. формируется служебный пакет активации, в поле MACPayload которого содержится текущее значение счетчика активаций Na, а в качестве адреса указывается DevAddr0 = CRC24(DevID). При этом поле MACPayload передается в открытом виде (не шифруется), а поле имитовставки MIC рассчитывается на ключе Km для номера Nn = 0. Сформированный служебный пакет активации должен быть отправлен MAX_PKT_TX_NUM раз подряд для повышения вероятности его доведения;
6. устройство считает активацию успешно завершенной и может передавать пакеты полезных данных.

Напомним формат пакета OpenUNB:

Сервер по приему пакета активации ищет адрес из пакета в списке адресов активированных устройств. Для каждого из найденных совпадений:

1. сохраняется полученное значение счетчика активаций устройства Na. Если для данного устройства ранее уже осуществлялась успешная активация, то сервер должен дополнительно проверить, что текущее значение Na больше чем значение Na, полученное при предыдущей успешной активации. Если эта проверка завершается неуспешно, то сервер переходит к следующему найденному устройству;
2. вырабатывается ключ активации Ka;
3. вырабатывается ключ расчета имитовставки Km для эпохи Ne = 0;
4. для пакета проверяется совпадение имитовставки MIC на ключе Km для номера Nn = 0.

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

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

Реализованные процедуры активации и другие процедуры безопасности доступны в исходниках здесь.

Наш бессменный мастер Интернета вещей deef137 всегда на связи и готов помочь с вопросами по коду.

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

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

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

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

• Интернет вещей по-русски. Минимализм и открытость OpenUNB
• Интернет вещей по-русски. Многоканальная мощь физуровня базовой станции OpenUNB
• Интернет вещей по-русски. Помехоустойчивое кодирование в OpenUNB
• Интернет вещей по-русски. Канальный уровень OpenUNB. Общие положения и адресация устройств
• Интернет вещей по-русски. Процедура активации OpenUNB

а также изучить первоисточник на сайте Сколтеха.

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

Чтобы обеспечить базу безопасности, у каждого устройства и сервера должно быть что-то общее, секретное, которое никто не знает. В OpenUNB это секретный ключ шифрования K0, имеющий длину k, равную 128 или 256 бит. Весь остальной протокол должен быть сделан так, чтобы этот базовый, основной ключ не стал бы известен никому никаким образом, а информация при этом была защищена. Поэтому базовый ключ претерпевает такое множество преобразований в своем стремлении встретиться с информацией.

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

В недрах устройства и сервера OpenUNB есть счетчик активаций Na и счетчик эпох Ne, которые остаются примерно одинаковыми в процессе работы системы. Сначала вырабатывается ключ активации:

Потом уже по ключу активации вырабатываются рабочие ключ шифрования Km и ключ имитозащиты Ke:

Для криптографических преобразований разработчики OpenUNB рекомендуется использовать блочный шифр Магма, который имеет длину блока n = 64 бита и длину ключа k = 256 бит, определенный в стандарте ГОСТ Р 34.12-2015.

Шифрование выглядит так:

где Nn номер пакета, а выработка имитовставки так:

где значение вектора P зависит от длины блока n и длины поля MACPayload. Пусть len
однобайтная целочисленная беззнаковая переменная, равная длине полезных данных
MACPayload в битах (переменная len может принимать значения 16 или 48), тогда:

если len = 48 и n = 64, то

в остальных случаях

Процедура CMAC24 здесь это криптопреобразование "режим выработки имитовставки" согласно ГОСТ.

Далее эти поля вставляются на свои места. Напомним схему формирования пакета:

Более подробно, со всеми деталями, вы можете прочитать о безопасности в OpenUNB в первоисточнике.

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

Как всегда, исходники крипто-преобразований от deef137 доступны на Github.

В последнее время коллеги по "цеху" независимо друг от друга стали спрашивать меня: как получить c одного SDR-приемника одновременно все каналы Bluetooth? Полоса ведь позволяет, есть SDR с выходной полосой 80 МГц и более. Можно, конечно, сделать это на ПЛИС, но время такой разработки будет довольно большим. Мне давно было известно, что сделать такое на GPU довольно просто, но чтобы так!

Стандарт Bluetooth определяет физический уровень в двух версиях: Classic и Low Energy. Спецификация есть здесь. Документ ужасно большой, читать его целиком опасно для мозга. К счастью, большие компании, производящие измерительную технику, имеют средства для создания наглядных документов по теме. Tektronix и National Instruments, например. У меня совершенно нет шансов в конкуренции с ними по качеству представления материала. Интересующихся прошу изучать по ссылкам.

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

Таким образом, нам нужно нарезать полосу 80 МГц на 79 фильтров с шагом настройки 1 МГц и, одновременно с этим, на 40 фильтров с шагом настройки 2 МГц. Частоты следования отсчетов с выходов фильтров должны быть 1 МГц и 2 МГц, соответственно.

Таким образом, нам необходимо две гребенки фильтров.

Для начала выберем параметры этих фильтров исходя из полос сигналов Bluetooth Classic и Bluetooth Low Energy. Нам нужны их импульсные характеристики, чтобы рассчитать нагрузку на вычислительное устройство фильтра. Здесь сразу стоит оговориться, что длины импульсных характеристик мы выбрали исходя из требований "быстрого" алгоритма фильтрации. Суть от этого не меняется. И число коэффициентов импульсной характеристики не должно быть слишком большим, чтобы фильтр был реализуем на вменяемой вычислительной аппаратуре.

Для фильтров с шагом 1 МГц выберем полосу пропускания ФНЧ (половина полосы пропускания полосового фильтра) 500 кГц, длину импульсной характеристики подгоним к 480 отводам. Для фильтров с шагом 2 МГц эти параметры выберем 1 МГц и 240 отводов, соответственно. Тип окна выбираем Кайзера. Рассчитаем импульсные характеристики в filterDesigner и выгрузим их в формате С-header:

Можно решать задачу лобовым способом: строить соответствующий по числу фильтров массив DDC (Digital Down Converter). Такой подход хорош для ПЛИС, где возможна экономия за счет уменьшения разрядности вычислителей первых ступеней. Также ПЛИС это наиболее энергетически-эффективный способ реализации. Но трудозатраты при этом способе наиболее высоки.

При выполнении гребенки фильтров на популярных нынче GPU появляется возможность реализации более хитрого алгоритма: полифазной гребенки фильтров на основе БПФ, который на CUDA доступен из библиотеки. В заграничной литературе алгоритм называется Polyphase or WOLA (Weight, Overlap and Add) FFT Filterbank. Лень к рисованию не дает мне возможности выполнить наглядное объяснение самостоятельно. В Сети есть много материалов по теме, особенно наглядный график выполнен здесь на странице 11 (огромное спасибо уважаемым авторам), вот он:

Железо выберем то, которое есть под рукой. Это плата ввода компании "Инструментальные Системы" FMC126P. О ней я уже писал в одной предыдущей статье. В разъем FMC платы вставлен субмодуль той же компании с трансивером AD9371 с полосой 100 МГц. Весь поток с трансивера может быть непрерывно передан в компьютер для обработки.

Выберем видео-карту с GPU GTX 1050. (Соврал, это она нас выбрала: это все что было под рукой, была выдрана из вычислителя для расчета антенн, но тем удивительней было увидеть рабочую гребенку). Перейдем к программной части.

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

Вот ядро, которое выполняет перемножение сигнала на окно и сложение, и обертка для его вызова:

__global__ void cuComplexMultiplyWindowKernel(const cuComplex *data, const float *window, size_t windowSize, cuComplex *result) {    __shared__ cuComplex multiplicationResult[480];    multiplicationResult[threadIdx.x] = cuComplexMultiplyFloat(data[threadIdx.x + windowSize / 4 * blockIdx.x], window[threadIdx.x]);    __syncthreads();    cuComplex sum;    sum.x = sum.y = 0;    if (threadIdx.x < windowSize / 4) {        for(int i = 0; i < 4; i++) {            sum = cuComplexAdd(sum, multiplicationResult[threadIdx.x + i * windowSize / 4]);        }        result[threadIdx.x + windowSize / 4 * blockIdx.x] = sum;    }}cudaError_t cuComplexMultiplyWindow(const cuComplex *data, const float *window, size_t windowSize, cuComplex *result, size_t dataSize, cudaStream_t stream) {    size_t windowStep = windowSize / 4;    cuComplexMultiplyWindowKernel<<<dataSize / windowStep - 3, windowSize, 1024, stream>>>(data, window, windowSize, result);    return cudaGetLastError();}

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

Гребенки были проверены на выходном спектре каналов в реальном времени. На вход AD9371 подавался сигнал генератора сигналов 2450 МГц, селективность фильтров соответствовала расчетной.

В планах: адаптация софта на плату XRTX и реализация поиска пакетов, если это кому-нибудь окажется нужно или будет свободное время.

Всю работу по софту выполнил gaudima, слава ему!

Software Defined Radio (программно-определяемая радиосистема) это метод замены работы по металлу (что, в принципе, полезно для здоровья) на головную боль программирования. SDR пророчат большое будущее и основным достоинством считается снятие ограничений в реализации радиопротоколов. Примером является метод модуляции OFDM (Orthogonal frequency-division multiplexing), которая стала возможна только методом SDR. Но есть в SDR и еще одна, чисто инженерная возможность, это возможность контролировать и визуализировать сигнал в любой произвольной точке с наименьшими усилиями.

Одним из интересных стандартов связи является наземное эфирное телевидение DVB-T2. 

Зачем? Конечно, можно просто не вставая включить телевизор, но смотреть там абсолютно нечего и это уже не моё мнение, а медицинский факт.

Если серьёзно, DVB-T2 разработан с очень широкими возможностями, в том числе:

• indoor применение
• модуляция от QPSK до 256QAM
• полоса пропускания от 1,7MHz до 8MHz
  

  Опыт приема цифрового телевидения по принципу SDR есть. Стандарт DVB-T есть в известном проекте GNURadio. Есть блок gr-dvbs2rx для стандарта DVB-T2 (все для того же GNURadio), но требующий предварительной синхронизации сигнала и он вдохновляет (отдельное thanks to Ron Economos).

  
  

VLF

Запись и анализ

from scipy.io import wavfileimport matplotlib.pyplot as pltfrom PIL import Image_, data = wavfile.read('websdr_recording_2020-11-06T15_00_00Z_23.4kHz_.wav')print("WAV: %d samples" % data.shape[0])for iw in range(400, 1024, 2):    print("Saving: {} of {}...".format(iw, 1024))    w, h = iw, 800    image = Image.new('RGB', (w, h))    px, py = 0, 0    for p in range(data.shape[0]):        image.putpixel((px, py), (0, data[p]//16, 0))        px += 1        if px >= w:            px = 0            py += 1            if py >= h:                break    image.save("image-%d.png" % iw)

Заключение

Доступ к среде (MAC, Media Access Control) в OpenUNB очень прост случаен и асинхронен. Этот вид доступа еще называют асинхронная ALOHA. Даже WiFi может похвастаться более сложным вариантом MAC. За счет этого упрощения оконечные устройства OpenUNB могут сильно экономить в потребляемой энергии и стоимости оборудования. Но такой способ доступа к среде приводит к ошибкам при передаче, которые чаще происходят группами. Поэтому, хотя и не только поэтому, помехоустойчивому кодированию в OpenUNB уделено достаточно много внимания.

В настоящее время примером качественно спроектированных систем радиосвязи являются стандарты сотовой связи. Этот факт доказывается колоссальным прогрессом в способах передачи информации по радио, изменившим всю нашу жизнь. Детали реализации стандартов сотовой связи даже используются в профильных университетах, как условия задач. Создатели OpenUNB также не стали изобретать чего-то нового в смысле помехоустойчивого кодирования, а взяли пример со стандарта Интернета вещей от 3GPP NB-IoT. Там при передаче в сторону базовой станции применяется полярное кодирование.

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

В настоящее время особую популярность набирает новый вид помехоустойчивых кодов, называемых полярными кодами. Как было доказано в [1], предложенные Ариканом полярные коды способны асимптотически достигать границы Шенона. Данное преимущество позволяет использовать полярные коды в современных телекоммуникационных системах мобильной связи. За довольно короткое время развития полярных кодов было предложено множество алгоритмов декодирования. Идея традиционного алгоритма декодирования [1] для полярных кодов заключается в последовательной оценке информационных бит. Таким образом, если на каком то шаге декодирования происходит ошибка, то и оценка всех остальных бит тоже будет ошибочной. Такой алгоритм декодирования известен, как алгоритм последовательного исключения (ПИ). Одним из способов преодоления зависимости от оценок предшествующих бит является использование списочного алгоритма Тала-Варди.

В настоящей статье рассматривается списочный алгоритм Тала Варди, предложенный в [2] для декодирования полярных кодов, который существенно уменьшает вероятность ошибки декодирование и позволяет реализовать декодирование почти по максимуму правдоподобия уже для небольшого размера списка (L = 16).

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

Матрица G называют ядром Арикана, а через m обозначают ее кронекеровскую степень. Формально алгоритм кодирования полярного кода состоит из двух основных этапов, а именно: формирования кодовой последовательности и умножения на матрицу Арикана. Под формированием кодового слова понимается вставка информационных бит в незамороженные позиции кодовой последовательности, и дальнейшее умножение этой последовательности на матрицу Арикана. Степень матрицы соотносится с длинной кодовой последовательности как N = 2^m.

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

Для начала давайте проверим идею, что полярные коды действительно так хороши для нашего случая. Для этого сравним их с обычными конкурентами: БЧХ, Рида-Соломона, Голея. (Здесь следует заметить, что полярный код чувствителен к виду модуляции и что он особенно хорош именно при DBPSK.) Проведем имитационное моделирование в Matlab вероятности битовой ошибки в зависимости от отношения сигнал-шум на бит (ОСШб) указанных кодов с примерно одинаковыми скоростями. Результаты моделирования приведены на рисунке. По графикам видно, что даже в области малых значений ОСШб полярный код немного, но лидирует.

Выигрыш в 1 дБ или меньше может показаться мелочью, не достойной усилий. Но подумайте о радиоинженере, которому вы предложите уменьшить коэффициент шума уже вылизанного до предела приемника на 1 дБ, чтобы догнать конкурентов. Или подумайте о создателе сети IoT, которому нужно будет ставить базовые станции на 10 процентов чаще, чем конкурентам.

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

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

int n_polar = _frozen_indicator.size();std::vector<uint8_t> iwd_s(n_polar);std::vector<int> inf_idx;std::vector<uint8_t> u(n_polar);for (int i = 0, j = 0; i < iwd_s.size(); i++) {    if (_frozen_indicator[i] == 0) {        iwd_s[i] = _iwd[j++];        inf_idx.push_back(i + 1);    }    else {        iwd_s[i] = 0;    }    u[i] = 0;}

Результатом работы данного алгоритма является промежуточное кодовая последовательность размером 128 или 196 бит, соответственно. Далее для того, что бы умножить промежуточную кодовую последовательность на матрицу Арикана, необходимо дополнить промежуточную кодовую последовательность нуля до целой степени двойки. Умножение на матрицу Арикана осуществляется с помощью функции, приведенной ниже:

return solve_recursively_prep(inf_idx, u, iwd_s, n_polar);

Декодер реализован в приложении на Raspberry. Декодер получает от демодулятора DBSPK мягкие решения и реализует алгоритм декодирования Тала Варди.

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

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

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

Декодер:

std::vector<std::vector<float>> prob;std::vector<std::vector<uint8_t>> dec = pcscl_prep(8, 16, llr, &prob, info_bit_pattern_96);dec = polar_transform_noperm(dec);dec = extract_with_filter(dec, crc_mask_96, num_of_nonzero_bits_96 - short_96);std::vector<uint8_t> crc_err;crc_err = crc_ok_array(0x327, dec);

Чтобы проверить соответствие реализации полярного кода идее, проводим натурное моделирование. Для этого создаем на столе такой стенд: подключаем RTL-SDR к Raspberry, включаем запись с эфира, запускаем передатчик и через аттенюатор записываем сигнал в файл. В софте читаем сигнал из файла, делаем измерение ОСШ и подмешивание к принимаемому сигналу шума. Далее запускаем процесс сбора статистики и уходим спать. По приходу мы имеем в распоряжении такой график:

График с точностью до погрешностей совпадает с графиком из модели в Matlab.

Попутно получаем график вероятности потери пакета в зависимости от ОСШ:

.

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

P.S.

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

[1] Arikan E. Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels // IEEE Transactions on Information Theory. 2009. July. Vol.55, no. 7. P. 30513073.
[2] Tal I., Vardy A. List decoding of polar codes // Proceedings of IEEE International Symposium on Information Theory. 2011. P. 15.

Аппаратная часть

От простого к сложному

Программная часть

Калибровка частоты

Unfinished Sympathy