Коды в гранично-ранговой метрике и их приложение тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Фам Хю Лок

• Фам Хю Лок
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Фам Хю Лок

Введение

Глава 1. Коды в гранично-ранговой метрике

1.1 Введение

1.2 Коды над конечными полями

1.3 Гранично-ранговые ошибки

1.4 Основы теории гранично-ранговых кодов

1.4.1 Основные понятия

1.4.2 Гранично-ранговое расстояние

1.4.3 Определения для гранично-ранговых кодов

1.4.4 Дуальные коды

1.5 Алгоритмы вычисления граничного ранга матрицы

1.5.1 Алгоритм на основе сравнения между векторами

1.5.2 Алгоритм на основе построения двудольного графа

1.6 Конструкция гранично-ранговых кодов

1.6.1 Описание конструкции

1.6.2 Сравнительные характеристики ранговых и гранично-ранговых кодов

1.7 Гранично-ранговые коды с различным расстоянием

1.7.1 Коды с гранично-ранговым расстоянием & = п

1.7.2 Коды с гранично-ранговым расстоянием ё, =

1.7.3 Коды с гранично-ранговым расстоянием ё, =

1.7.4 Коды с гранично-ранговым расстоянием ё, = п —

1.7.5 Коды с гранично-ранговым расстоянием ё, =

1.7.6 Общая конструкция

1.7.7 Построение кодов, не являющихся кодами МГГГ

Глава 2. Новый алгоритм декодирования гранично-ранговых

кодов

2.1 Коды, исправляющие одиночные решетчатые ошибки

2.1.1 Основная теорема и идея декодирования

Стр.

2.1.2 Алгоритм декодирования

2.1.3 Моделирование алгоритма для кода С[4 х 4,2 • 4,3]

2.2 Коды, исправляющие двойные решетчатые ошибки

2.2.1 Основная теорема и идея декодирования

2.2.2 Алгоритм декодирования

2.2.3 Моделирование алгоритма для кода С[5 х 5,1 • 5,5]

2.3 Декодирование по синдрому

2.3.1 Основная идея декодирования

2.3.2 Алгоритм декодирования

2.3.3 Временная сложность алгоритма

2.4 Списочное декодирование

2.4.1 Определение

2.4.2 Верхняя граница Джонсона

Глава 3. Приложение гранично-рангового кода

3.1 Применение гранично-ранговых кодов в системах хранения данных

3.1.1 Гранично-ранговые коды для дисковых массивов

3.1.2 Гранично-ранговые коды для систем распределенного хранения данных

3.2 Применение гранично-ранговых кодов в криптосистеме

3.2.1 Линейные коды в криптосистеме с открытым ключом

3.2.2 Система ГПТ

3.2.3 Выводы

Заключение

Список сокращений и условных обозначений

Словарь терминов

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

Список рисунков

Список таблиц

Стр.

Приложение А. Листинг программного кода

Приложение Б. Результаты работы с таблицами

Б.1 Код С[5 х 7,3 • 7,3]

Введение диссертации (часть автореферата) на тему «Коды в гранично-ранговой метрике и их приложение»

Введение

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

Современные телекоммуникационные системы часто используют каналы параллельной передачи информации. В системе параллельных каналов связи с помехами, можно рассматривать каждое сообщение как двоичную матрицу размера т х п, где число каналов равно т, длительность передачи по каждому из каналов равна п. Для таких образцов больше подходит гранично-ранговая метрика, которая была введена Э.М. Габидулиным [1],[2].

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

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

В литературе описаны оптимальные коды или коды с максимальным гранично-ранговым расстоянием (МГГГ) над СГ(дтхп). Для конструкции известных кодов строится алгоритм декодирования. Актуальной научной проблемой является поиск и исследование других оптимальных кодов с различным расстоянием и построение алгоритма декодирования для них.

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

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

Особый интерес представляет криптосистема с открытым ключом на основе линейных кодов. Главная трудность заключается в решении задачи декодирования сообщения с добавленными искусственными ошибками. Помимо добавленных ошибок код может исправлять обычные ошибки, которые появляются при передаче информации. Мак-Элис [3] представил первую основанную на коде криптосистему с открытым ключом (ГКС). Система основана на кодах Гоппы в метрике Хемминга, что связано с трудностью общей задачи декодирования. Эта криптосистема является сильной, но размер открытого ключа слишком большой (60 КБ) для эффективной реализации. После этого ГКС, основанная на семействе общих кодов Гида-Соломона, была представлена Нидеррейтером; размер его открытого ключа меньше, чем у криптосистемы МакЭлиса, но это все еще большой размер для реального использования [4]. В 1991 году Габидулин, Парамонов и Третьяков предложили новую криптосистему с открытым ключом, которая теперь называется криптосистемой ГПТ [5]. Криптосистема ГПТ имеет два преимущества по сравнению с криптоси-

стемой Мак-Элиса. Во-первых, она более устойчива к атакам декодирования, чем криптосистема Мак-Элиса; во-вторых, размер ключа ГПТ намного меньше и более полезен с точки зрения практического применения, чем криптосистема Мак-Элиса.

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

Для достижения поставленной цели в работе необходимо рассмотреть следующие задачи:

1. Исследование теории кодов в гранично-ранговой метрике.

2. Построение алгоритма вычисления граничного ранга двоичной матрицы.

3. Исследование конструкции гранично-ранговых кодов над полем GF (qmxn).

4. Поиск новых кодов с максимальным гранично-ранговым расстоянием (МГРР) в гранично-ранговой метрике.

5. Разработка алгоритмов декодирования произвольных кодов.

6. Исследование возможностей применения гранично-ранговых кодов в системах хранения данных и криптосистемах с открытым ключом.

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

1. Исследована теория кодов в гранично-ранговой метрике. Гранично-ранговые ошибки исправлены в массивах микросхем памяти, в записи магнитной ленты, в демодуляции FSK или в передачах OFDM и FDM.

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

3. Исследована конструкция гранично-ранговых кодов над полем GF (qmxn).

4. Найдено новое семейство оптимальных кодов в гранично-ранговой метрике, имеющих расстояние d = п,п — 1,2,3. С повышенной корректирующей способностью за счет исправления ошибок.

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

6. Исследованы методы применения системы шифрования с открытым ключом, использующие коды в гранично-ранговой метрике.

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

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

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

Основные положения, выносимые на защиту:

1. Алгоритмы вычисления граничного ранга матрицы, включая оценку характеристики кодов в гранично-ранговой метрике.

2. Метод построения линейных кодов над полем СГ(дтхп) с определенным гранично-ранговым расстоянием, включающих МГРР коды для расстояния (1.

3. Метод декодирования гранично-ранговых кодов для одиночных, двойных решетчатых ошибок и декодирование по синдрому.

4. Метод применения гранично-ранговых кодов для дисковых массивов в системах хранения данных.

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

— 61-й Всероссийской научной конференции Московского физико-технического института, Долгопрудный, 2018 г.

— 316(11), 320(15), 332(27), 335(30) и 343(37) научных семинаров на кафедре радиотехники и систем управления Московского физико-технического института, Долгопрудный, 2018-2020.

— 6th NAFOSTED Conference on Information and Computer Science, NICS, Hanoi, Vietnam, 2019.

— на научном семинаре по теории кодирования Института Проблем Передачи Информации, Москва, 2020 г.

— XXVI международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика, МЭИ", Москва, 2020 г.

— 63-й Всероссийской научной конференции Московского физико-технического института, Долгопрудный, 2020 г.

— VII Международной конференции «Инжиниринг & Телекоммуникации», Еп&Т-2020, Долгопрудный, 2020 г.

Результаты диссертации обсуждались на научных семинарах кафедры радиотехники МФТИ.

Публикации. Основные результаты по теме диссертации изложены в 7 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ROSI. 2 и периодических научных журналах, индексируемых Web of Science и Scopus, 1 — в тезисах докладов, 1 — заявка на изобретение.

Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и двух приложений. Полный объём диссертации составляет 125 страниц, включая 18 рисунков и 9 таблиц. Список литературы содержит 67 наименований.

Работа построена следующим образом.

Первая глава посвящена кодам в гранично-ранговой методике. Сначала написаны некоторые известные важные определения и кодовое расстояние в гранично-ранговой метрике, а затем рассматривается конструкция кодов. Для вычисления граничного ранга матрицы построены два алгоритма, основанные на сравнении векторов и построении двудольного графа. Помимо известных гранично-ранговых кодов, приведены другие конструкции. Для поддержки и проверки конструкции кодов использованы алгоритмы вычисления граничного ранга матрицы. Полученные результаты, представленные в первой главе, опубликованы в [6; 7].

Вторая глава посвящена алгоритмам декодирования гранично-ранговых кодов. Вначале описывается алгоритм декодирования гранично-ранговых кодов, исправляющих одиночные решетчатые ошибки. Представлено моделирование результата исправления одиночной ошибки для кода С[4 х 4,2 • 4,3]. Для кодов, исправляющих двойные решетчатые ошибки, построен алгоритм декодирования этих кодов в гранично-ранговой метрике. Далее предлагается моделирование результата исправления одиночной ошибки для кода С[5 х 5,1 • 5,5]. В конце главы приводится верхняя граница Джонсона на размер списка и сравнивается с известными результатами в метрике Хэмминга и ранговой метрике. Из этого результата представлен алгоритм списочного декодирования за полиномиальное время до границы Джонсона. Кроме того, для каждого алгоритма оценивается время выполнения. Полученные результаты, представленные в второй главе, опубликованы в [8—10].

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

В заключении сформулированы основные результаты диссертационной работы.

Глава 1. Коды в гранично-ранговой метрике

Коды в гранично-ранговой метрике длины п ^ т можно рассматривать как множество т х п матриц над конечным полем ^ или эквивалентно как множество векторов длины п над полем расширения Граничный ранг такого "слова" - это просто граничный ранг матрицы представления, а гранично-ранговое расстояние между двумя словами - это граничный ранг их разности. Эти определения основаны на том факте, что гранично-ранговая метрика действительно является метрикой. Некоторые кодовые конструкции и основные свойства в гранично-ранговой метрике демонстрируют сильное сходство с кодами в метрике Хэмминга.

В первой главе приводятся некоторые важные теории линейных кодов и в основном рассматриваются коды в гранично-ранговой метрике. Предложено пространство квадратных матриц над конечным полем. Также будут построены новые алгоритмы вычисления граничного ранга двоичной матрицы.

1.1 Введение

Первая работа была исследована о гранично-ранговой метрике - это "Коды, исправляющие ошибки решетчатой конфигурации" [1], опубликованной в 1972 году. Термин "гранично-ранговое расстояние", описывающий расстояние между двумя матрицами или кодовое расстояние, начал формироваться Э.М. Габидулиным и В.И. Коржиком. Далее Э.М. Габидулин дополнял и усовершенствовал гранично-ранговую метрику, которая сегодня принято многими исследователями, занимающихся проблемой передачи информации. Эта работа была предложена Э.М. Габидулиным в 1985 году [2].

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

Определение 1. Пусть - множество всех матриц над ^ с т строками и п столбцы.

Определение 2. Расстоянием между матрицами А\ к А2 называется граничный ранг их разности:

¿(Аг,А2) = р(Лх - А'1)

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

Определение 3. Кодом объема М называется произвольное множество матриц Vl,V2,..., Ум одинаковой размерности.

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

к

0.2 0.4 0-5360.6 0.8

ё

п

Гисунок 1.1 — Зависимость скорости передачи Я от относительного кодового

расстояния -.

* п

На рис. 1.1 приведены асимптотические зависимости методов для случая т = п ^ ж. Из рисунка видно, что итеративные коды (кривая 2) уступают

0

1

оптимальным (кривая 1) во всем диапазоне, а коды, построенные по первому методу (кривая 3), применимы лишь при малом числе искаженных строк и столбцов - < 0.536.

^ п

Пусть информационные символы будут х = (хг ). Тогда кодовая

матрица, соответствующая этому сообщению, имеет вид

^Х\ Х'2 . . . Хп— г Хп ^

V =

Хп Х\ . . . Хп—2 Хп—г

ух2 Х- ... Хп XI у

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

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

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

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

1. ё, = 2, ^произвольно, Я = Ятах. Коды оптимальны.

2. <1 = 3, ^произвольно, Я = Ятах--ф-. Коды асимптотически оптимальны.

3. <1 = 4, ^произвольно, Я = Ятах — Коды асимптотически оптимальны.

4. <1 = рт — 1, N = ртт, в - целые, р - простые, Я = Ятах — 2- Коды асимптотически оптимальны.

Диссертационная работа посвящена разработке кодов в гранично-ранговой методике, болле конкретно, новым семействам гранично-ранговых кодов с различным гранично-ранговым расстоянием и алгоритмам декодирования

гранично-ранговых кодов. В приложении гранично-ранговых кодов рассматриваются система хранения данных и криптосистема с открытым ключом.

1.2 Коды над конечными полями

Этот подраздел содержит обозначения, касающиеся конечных полей, не вдаваясь в детали их теории. Обширное исследование конечных полей, их свойств и приложений можно найти в стандартной литературе о конечных полях, например, [12; 13], а также в книгах по теории кодирования, например, [14; 15].

Пусть р - простое число, тогда ^ = {0,1,... ,р — 1} обозначает простое поле порядка р. Пусть д - степень простого числа р, тогда через ^ обозначим конечное поле порядка д. Это конечное поле ^ содержит д элементов и р называется его характеристикой. Поле расширения (степени расширения т) ^ обозначается . Это поле расширения можно постройть из ^ и полинома р(х) степей и т, который неприводим коэффициенты которого находятся

в Для люб ого т существует, по крайней мере, один такой неприводимый многочлен степени т.

Поле расширения может быть представлено в виде векторного пространства над используя базис Б = {во,въ ... ,вт—1} из над

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

— Для любого целого числа г мы обозначаем д степейь [г] гак дг.

— Для любого а € ^т : = а и для любого а € ^т и целого чиела г, д-степень вычисляется по модулю т: а[г] = а[г тоЛ т]

— Для любого А € ^ и любого целого числа г: А[г] = А.

_ для ЛЮ50Г0 а,Ь в ¥(1ш и любого целого числа г: (а + Ь)® = а® + ЬМ.

Множество всех подпространств в ^ называется проективным пространством и обозначается (п). Грассманиан размерности к является множеством всех подпространств в ^размерности к ^ п и обозначается Яя (п,к). Ясно, что проективное пространство имеет вид (п) = УП=0 = 0^(п,к). Мощность 0Я(п,к) задается следующим образом.

Лемма 1. (Количество подпространств)

Число к-мерных подпространств в Г™ над ^ равно

к-1

ф — дг

=0 1к — Ч'

п

^сд0д^зуется для обозначения множествавсех матриц с размером в х п над ^ и = Р^™ - для множества всех векторов строки длины п над ^т.

Задано множество Л (например, векторов или матриц). Чтобы определить коды с исправлением ошибок, нам нужно измерить расстояние между элементами в этом наборе. Мера расстояния на этом множестве Л называется метрикой, если она удовлетворяет следующим условиям.

Определение 4. (Метрика)

Пусть Л - множество (например, векторов или матриц). Мера расстояния ^д(а,Ъ) на любых двух элементах а,Ь в этом множестве Л является метрикой, если она удовлетворяет всем а, Ъ, с € А:

— положительная определенность: (1д(а, Ъ) ^ 0, где ^д(а, Ъ) = 0 тогда

а=Ъ

— симметрия: ^д(а, Ъ) = (1д(Ъ, а),

— неравенство треугольника: ^д(а, Ъ) + (1д(Ъ, с) ^ ^л(а, с).

Классические коды с исправлением ошибок определены в метрике Хем-минга, и они были предметом большого количества публикаций. Среди кодов в метрике Хемминга известны классы кодов Хемминга [16], коды Рида-Мюллера [17; 18] коды Рида-Соломона [19], циклические коды [20], а также многие другие. В этом тезисе рассматриваются коды в гранично-ранговой метрике. Эта метрика будет дана в подразделе 1.4.3 для блочных кодов в Гдш.

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

Определение 5. (Блочный код).

Пусть задана метрика в удовлетворяющая требованиям определения

Блочный код С (п, М, (!) над ^ представляет собой множество векторов в от мощности М, где минимальное расстояние (в данной метрике) между любыми двумя векторами этого кода равно (1.

Блочный код С над ^ называется линейным, если он является ^-мерным подпространством в над а его параметры обозначены [п, к, ¿]. Параметр к называется размерностью С.

Фракция Я = (1одяМ)/п называется кодовой скоростью С. Если С линейна, то Я = к/п.

Все векторы в ^^ называются информационными словам и. Векторы в ^ в (п, М, d)-к(щe называются кодовыми словами. Мощность линейного блочного кода С[п, к,$] над следовательно, равна М = дк и так как С является подпространством в для любых кодовых слов с(1), с(2) € С и любых элементов а,Ь € ^ линейная комбинация ас(1) + 6с(2) также является кодовым словом С.

Определение 6. (Порождающая матрица)

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

Порождающая матрица может использоваться для кодирования информационных слов в Гк в кодовые елова в Таким образом, кодовым словом

7>п Ч

кода [п, к, d] является любой вектор в F™ который можно получить с помощью

u • G для некоторого и Е Fy. Кодирование определяет биективное отображение

7к ч

информационных векторов в Fk на кодовые ело ва в F'"".

encode: F™ ^ F™

u = (щ Щ ... Uk-i) ^ С = (со С\ ... Cn-i)

Заметьте, что для данного [п, к, d] кода С существует более одной порождающей матрицы, поскольку можно использовать любой базис ^-мерного подпространства С тад Fq в произвольном порядке.

Определение 7. (Дуальный код)

Для двух векторов a, b Е пусть (a, Ъ) = ^определяют скалярное произведение, и пусть С - лииейн ый [n,k,d] код над Fq. Тогда множество векторов

С± = {c^ Е F™ : (c^,c) = 0, Vc Е С]

называется дуальным кодом для С.

Лемма 2. Если код С[п, к, д] - линейный над Еч, то дуальный код С1 также линейный над Еч, и С11 = С.

Дуальный код [п,к,^] кода над ^ также является линейным кодом над ^ и имеет размерность к1 = п — к и дайну п. Его минимальное расстояние обозначается через ё,1., но его значение не обязательно определяется параметрами кода [п, к, Следовательно, дуальный код С1 является кодом [п, п — к, ё,1]., то есть (п — к) -мерным подпространством в которое может использоваться для определения проверочной матрицы кода С.

Определение 8. (Проверочная матрица)

Матрица Н с размером (Ж — к) х п над ¥(1 называется проверочной матрицей [п,к,ё\ код а С над ^ тогда и только тогда, когда она является порождающей матрицей дуальной кода С1[п, п — к, (I1 ] над

Таким образом, для любого с € С умножение с проверочной матрицей дает с • НТ = 0 и С • Нт = 0.

Определение 9. (Синдром)

Для любого а € ^ и проверочной мат рицы Н код а С [п, к, векто р 8 = а • Нт называется синдромом а.

Если и только если а € С, то синдром 8 = 0.

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

Лемма 3. (Возможность декодирования)

Пусть С (п, М, (!) - блочный код над ^ с минимальным расстоянием (1 в данной метрике ¿а и пусть г - слово в Г™.

Тогда, существует не более одного кодового слова, с € С, такого, что ¿а(г, с) ^ т = [(<! — 1)/2]. Кроме того, если существует такое кодовое слово с € С, чтобы 0 < (1А(г, с) ^ (I — 1, то г € С.

Лемма 3 показывает, что всегда можно однозначно декодировать до Ь = [^ — 1)/2] ошибок и обнаруживать до ё, — 1 ошибок.

1.3 Гранично-ранговые ошибки

В некоторых приложениях возникает следующая проблема ошибок: информационные символы должны храниться в (т х п) массивах. Некоторые из этих символов по ошибке записаны таким образом, что все искаженные символы находятся в одном или нескольких строках или столбцах (или обоих). Мы называем такие ошибки как ошибки решетчатой конфигурации. На рисунке 1.2 показана схема ошибки решетчатой конфигурации, все искаженные символы сосредоточены в трёх столбах и двух строках. Эти ошибки решетчатой конфигурации могут быть найдены в массивах микросхем памяти [21], [22], [23] или в записи магнитной ленты [24], [25], [26].

Рисунок 1.2 — Схема ошибки решетчатой конфигурации

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

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

Рисунок 1.3 — Система параллельных каналов связи с помехами

Э.М. Габидулиным [27], [1], [2] были введены граничные коды, исправляющие ошибки решетчатой конфигурации. Коды могут исправить ошибочные строки и столбцы.

Time

\

1 2 ... -> п

1 Xi,2 . . .

C = 2 Х2,1 Х2,2 . . .

Frequency

. т у %т,1 %т,2 . . .

C + Е, где C - ■ кодовая матрица, R -

/

Е - матрица ошибки. Пусть граничный ранг р(Е) = 2 и предположим, что матрица Е:

/о 1 0 0 о\ 0 0 0 0 0 Е = 110 0 1 0 10 0 0 00000

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

1.4 Основы теории гранично-ранговых кодов

Список литературы диссертационного исследования кандидат наук Фам Хю Лок, 2021 год

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

1. Габидулин Э.7 Коржик В. Коды, исправляющие ошибки решетчатой конфигурации // Известия высших учебных заведений. Радиоэлектроника. — 1972. - т. 15, № 4. - с. 492 498.

2. Габидулин Э. М. Оптимальные коды, исправляющие ошибки решетчатой конфигурации // Проблемы передачи информации. — 1985. — т. 21, № 2. — с. ЮЗ—108.

3. McEliece R. J. A public-key cryptosystem based on algebraic // Coding Thv. — 1978. - т. 4244. - c. 114 116.

4. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Prob. Control and Inf. Theory. - 1986. - т. 15, № 2. - с. 159^166.

5. Gabidulin E. M.. Paramonov A., Tretjakov 0. Ideals over a non-commutative ring and their application in cryptology // Workshop on the Theory and Application of of Cryptographic Techniques. — Springer. 1991. — c. 482 489.

6. Фам X. Л. Алгоритм вычисления граничного ранга двоичной матрицы // Труды МФТИ. - 2019. - т. И, № 1. - с. 62 68.

7. Фам, X. Л. Коды в гранично-ранговой метрике // Труды МФТИ. — 2019. — т. И, № 2. - с. 69 77.

8. Pham H. L. Construction of new codes in term-rank metric // IET Communications. - 2020. - Vol. 14, no. 8. - P. 1215-1220.

9. Pham H. L., Le T. T. L. Coding in Term-rank Metric 11 6th NAFOSTED Conference on Information and Computer Science. — 2019. — P. 18—22.

10. Фам X. Л. Коды, исправлящие двойные решетчатые ошибки в гранично-ранговой метрике // XXVI Международная научно-техническая конференция студентов и аспирантов МЭИ. — 2020.

11. Pham H. L. Term-rank Codes for Data Storage Systems // 2020 International Conference on Engineering and Telecommunication (EnT). — IEEE. 2020. — P. 1 4. — (Scopus).

12. Lid,I R., Niederreiter H. Finite fields, т. 20. — Cambridge university press, 1997.

13. Applications of finite fields, t. 199 / A. J. Menezes [h pp.]. — Springer Science & Business Media, 2013.

14. Godsil C. Algebraic combinatorics. — Routledge, 2017.

15. Huffman W., Pless V. Fundamentals of Error-Correcting Codes. — Cambridge University Press, 2010.

16. Hamming R. W. Error detecting and error correcting codes // The Bell system technical journal. - 1950. - t. 29, № 2. - c. 147 160.

17. Reed I. S. A class of multiple-error-correcting codes and the decoding scheme : Tex. oth. / MASSACHUSETTS INST OF TECH LEXINGTON LINCOLN LAB. - 1953.

18. Muller D. E. Application of Boolean algebra to switching circuit design and to error detection // Transactions of the IRE professional group on electronic computers. — 1954. - c. 6 12.

19. Reed I. S., Solomon G. Polynomial codes over certain finite fields // Journal of the society for industrial and applied mathematics. — 1960. — t. 8, № 2. — c. 300^304.

20. Bose R. C., Ray-Chaudhuri D. K. On a class of error correcting binary group codes // Information and control. — 1960. r. 3. A" 1. c. 68^79.

21. Levine L., Meyers W. Special feature: Semiconductor memory reliability with error detecting and correcting codes // Computer. — 1976. — Vol. 9, no. 10. — P. 43-50.

22. Chen C.-L., Hsiao M. Error-correcting codes for semiconductor memory applications: A state-of-the-art review // IBM Journal of Research and development. - 1984. - Vol. 28, no. 2. - P. 124-134.

23. Mikhail W., Bartoldus R., Rutledge R. The reliability of memory with single-error correction // IEEE Transactions on Computers. — 1982. — No. 6. — P. 560-564.

24. Blaum M.. McEliece R. Coding protection for magnetic tapes: A generalization of the Patel-Hong code (Corresp.) // IEEE Transactions on Information Theory. - 1985. - Vol. 31, no. 5. - P. 690-693.

25. Cideciyan R. D., Furrer S.7 Lantz M. A. Product codes for data storage on magnetic tape // IEEE Transactions on Magnetics. — 2016. — Vol. 53, no. 2. — P. 1-10.

26. Prusinkiewicz P., Budkowski S. A double track error-correction code for magnetic tape // IEEE Transactions on Computers. — 1976. — No. 6. — P. 642-645.

27. Gabidulin E. A class of two-dimensional codes correcting lattice-pattern errors // Proc. of the 2-nd International Symposium on Information Theory. — 1971. - c. 44^47.

28. Габидулин Э. Лекции по алгебраическому кодированию. — Москва : МФТИ, 2015. - 62 с.

29. Stinson D., Wei R., Paterson M. B. Combinatorial batch codes // Advances in Mathematics of Communications. — 2009. — Vol. 3, no. 1. — P. 13—27.

30. Lund D., Gabidulin E. M.. Honary B. A new family of optimal codes correcting term rank errors // 2000 IEEE International Symposium on Information Theory (Cat. No. 00CH37060). - IEEE. 2000. - P. 115.

31. Wachter-Zeh A. List decoding of crisscross errors // IEEE Transactions on Information Theory. — 2016. - Vol. 63, no. 1. - P. 142-149.

32. Blaum, M.. В ruck J. MDS array codes for correcting a single criss-cross error / / IEEE Transactions on Information Theory. — 2000. — Vol. 46, no. 3. — P. 1068-1077.

33. Wachter-Zeh A. List decoding of crisscross error patterns // 2014 IEEE International Symposium on Information Theory. — IEEE. 2014. — P. 1236—1240.

34. Wachter-Zeh A. Bounds on list decoding of rank-metric codes // IEEE Transactions on Information Theory. — 2013. — Vol. 59, no. 11. — P. 7268—7277.

35. Delsarte P. Bilinear forms over a finite field, with applications to coding theory // Journal of Combinatorial Theory, Series A. — 1978. — Vol. 25, no. 3. — P. 226-241.

36. Альпин Ю. А., Ильин С. H. Дискретная математика: графы и автоматы. Учебное пособие. - Казань : Казанский государственный университет им. В.И. Ульянова-Ленина, 2006. — 78 с.

37. Dénes К. Grâfok és mâtrixok // Matematikai és Fizikai Lapok. — 1931. — т. 38. - c. 116—119.

38. Hopcroft J. E., Karp R. M. An пл5/2 algorithm for maximum matchings in bipartite graphs // SIAM Journal on computing. — 1973. — т. 2, № 4. — с. 225—231.

39. Ford Jr L. R., Fulkerson D. R. Flows in networks, т. 54. — Princeton university press, 2015.

40. Gabidulin E. M. Theory of codes with maximum rank distance // Problemy Peredachi Informatsii. — 1985. т. 21. Л'° 1. с. 3—16.

41. Sidorenko V. R., Bossert M., Gabidulin E. M. Generalized minimum distance decoding for correcting array errors // International Zurich Seminar on Communications-Proceedings. — Eidgenössische Technische Hochschule Zürich. 2010.

42. Галлагер Р. Теория информации и надежная связь // М.: Сов. радио. — 1974. - т. 720.

43. Guruswami V. List decoding of error-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition, т. 3282. — Springer Science & Business Media, 2004.

44. Elias P. List decoding for noisy channels. — 1957.

45. Wozencraft J. M. List decoding // Quarterly Progress Report. — 1958. — т. 48. - c. 90 95.

46. Johnson S. A new upper bound for error-correcting codes // IRE Transactions on Information Theory. - 1962. - т. 8, № 3. - с. 203^207.

47. Вассалы,го Л. А. Новые верхние границы для кодов, исправляющих ошибки // Проблемы передачи информации. — 1965. — т. 1, № 4. — с. 41^44.

48. Micheloni R., Marelli A., Ravasio R. Error correction codes for non-volatile memories. — Springer Science & Business Media, 2008.

49. Vasic В., Kurtas E. M. Coding and signal processing for magnetic recording systems. — CRC press, 2004.

50. Thomasian A., Blaum, M. Higher reliability redundant disk arrays: Organization, operation, and coding // ACM Transactions on Storage (T0S). - 2009. - т. 5, № 3. - с. 1 59.

51. Patterson D. A., Gibson G.7 Katz R. H. A case for redundant arrays of inexpensive disks (RAID) // Proceedings of the 1988 ACM SIGMOD international conference on Management of data. — 1988. — c. 109—116.

52. Network coding for distributed storage systems / A. G. Dimakis [h ,np.] // IEEE transactions on information theory. — 2010. — t. 56, № 9. — c. 4539 4551.

53. Pieprzyk J., Hardjono T., Seberry J. Fundamentals of computer security. — Springer Science & Business Media, 2013.

54. Diffie W., Hellman M. New directions in cryptography // IEEE transactions on Information Theory. — 1976. — t. 22, № 6. — c. 644 654.

55. Merkle R., Hellman M. Hiding information and signatures in trapdoor knapsacks // IEEE transactions on Information Theory. — 1978. — t. 24, № 5. - c. 525 530.

56. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. — 1978. — t. 21, ..V" 2. - c. 120—126.

57. De Dormale G. M.. Quisquater J.-J. High-speed hardware implementations of elliptic curve cryptography: A survey // Journal of systems architecture. — 2007. - t. 53, № 2/3. - c. 72 84.

58. Tibouchi M.. Kim T. Improved elliptic curve hashing and point representation // Designs, Codes and Cryptography. — 2017. — t. 82, № 1/2. — c. 161—177.

59. Selecting elliptic curves for cryptography: An efficiency and security analysis / J. W. Bos [h /i,p.] // Journal of Cryptographic Engineering. — 2016. — t. 6, ..V" 4. - c. 259 286.

60. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE transactions on information theory. — 1985. — t. 31, № 4. - c. 469 472.

61. Berlekamp E., McElieœ R., Van Tilborg H. On the inherent intractability of certain coding problems (corresp.) // IEEE Transactions on Information Theory. - 1978. - r. 24. ..V 3. - c. 384 386.

62. Heiman R. On the security of cryptosystems based on linear error correcting codes. — 1987.

63. Adams С. Л/.. Meijer Н. Security-related comments regarding McEliece's public-key cryptosystem // Conference on the Theory and Application of Cryptographic Techniques. — Springer. 1987. — c. 224 228.

64. Lee R., Brickell E. An Observation of the McEliece Public Key Cryptosystem." // Advances in Cryptology-EUROCRYPT88. —.

65. Сидельпиков В. Л/.. Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. _ 1992. _ т. 4? ^ 3. - с. 57 63.

66. Gibson J. К. Equivalent Goppa codes and trapdoors to McEliece's public key cryptosystem // Workshop on the Theory and Application of of Cryptographic Techniques. — Springer. 1991. — c. 517—521.

67. Gabidulin E. M. Public-key cryptosystems based on linear codes. — Citeseer, 1995.

Список рисунков

1.1 Зависимость скорости передачи Я от относительного кодового расстояния -..................................................................12

1 п

1.2 Схема ошибки решетчатой конфигурации................................18

1.3 Система параллельных каналов связи с помехами......................19

1.4 Радиус декодирования расстояния £........................................23

1.5 Блок-схема алгоритма вычисления граничного ранга матрицы .... 28

1.6 Пример двудольного графа................................................34

1.7 Построение потоковой сети................................................35

1.8 Поиск максимального потока в потоковой сети..........................35

1.9 Пример вычисления граничного ранга с помощью алгоритма Форда-Фулкерсона в потоковой сети......................................37

2.1 Закодированный блок данных, храненный в одной матрице ..........59

2.2 Код с расстоянием ^ не может исправить (1/2 ошибки..................83

2.3 Нормированный радиус Джонсона Ту/п в зависимости от нормированного минимального гранично-рангового расстояния

Ь = ¿/п......................................................................88

3.1 Модель чтения/записи данных............................................91

3.2 Гранично-ранговые коды для дисковых массивов......................95

3.3 Гранично-ранговые коды С[4 х 4, 2 • 4,3] для дисковых массивов ... 95

3.4 Гранично-ранговый код й информационными узлами и т — в проверочными узлами......................................................98

3.5 Криптосистема с открытым ключом...................100

3.6 Схема моделирования криптосистемы..................101

Список таблиц

1 Время выполнения алгоритма со сложностью 0(п4) зависимости от

п при скорости 2 * 109 (2СНг) операций в секунду........... 32

3 Результат вычисления граничных рангов всех сопровождающих матриц Е3.................................. 45

4 Результат вычисления граничных рангов всех сопровождающих матриц Е5.................................. 48

5 Результат вычисления граничных рангов всех сопровождающих матриц Е4.................................. 54

6 Результат вычисления граничных рангов всех кодовых матриц С . . 54

7 Результат вычисления граничных рангов всех кодовых матриц С . . 64

С

9 Результат вычисления граничных рангов всех сопровождающих

матриц Г7..................................123

Приложение А Листинг программного кода

Листинг А.1 Код Matlab, termrank.m, для алгоритма вычисления граничного ранга матрицы на основе сравнения между векторами function у = termrank(A) if ~ismatrix(А)

error('Input must be a matrix')

end

5 [m,n] = size (A) ; norm = 0; S = sum(A) ; R = sum(A ,2) ' ; max_S = max (S) ; 10 max_R = max(R);

while(max_S >0)

if (max_S >max_R)

%disp(} max_S>max_R '); for i=l:n 15 if (max_S == S (i))

A(:,i)=0; norm = norm +1;

end

end

20 elseif (max_S < max_R)

%disp(} max_S<max_R '); for j-1 : m

if (max_R == R (j ) ) A(j , :)=0;

25 norm = norm +1;

end

end

else

%disp(} max_S-max_R '); 30 if mycompare(R,S)==1

for j-1:m

if (max_R == R (j ) ) A(j , :)=0; norm = norm +1; 35 end

end

else

for i=l:n

if (max_S == S ( i)) A(: , i) =0 ; norm = norm +1;

end

45

end

end

end

50

Xdisp (A) ; S = sum(A) ; R = sum (A ,2) ' ; max_S = max(S); max_R = max(R);

end

% y - norm;

y=min(norm,min(m,n));

end

В Листинге A.l используется функция сравнения двух векторов, которая приведена в листинге А.2.

Листинг А.2 функция сравнения двух векторов

function у = mycompare(R,S) %return 1 if R>-S; if (~isvector(R) || ~isvector(S))

error('Input must be two vectors')

5 end

S_sort = sort(S,'descend ') ; n = size(S , 2) ;

R_sort = sort(R,'descend ') ; m=size(R , 2) ;

10

k = 1 ;

flag = 1 ; % R >= S

while 1

if k > min (m , n)

15

break

end

if R_sort(k) < S_sort(k)

flag=0;

20

break

end

if R_sort(к) > S_sort(к) flag=l; break

end

25 k = k + l;

end

У~ flag;

end

Листинг А.З Код Matlab, maxBPM.m, для алгоритма вычисления граничного

ранга матрицы на основе построения двудольного графа

% Program code Matlab to find % Maximum Bipartite Matching % Example

%>> A - [1 1 0 1 0; 110 10; 01010; 1 0 0 0 0]; 5 % >> maxBPM(A) % ans - 3

function у = maxBPM(A) if ~ismatrix(A)

error('Input must be a matrix') 10 end

% M is number of rows % and N is number of columns [M,N] = size(A) ;

15

20

25

% Initially all columns are available mat chR = zeros(1,N) ; matchR(:)=-1;

% count of rows assigned to columns result = 0; for u=l:M

% Mark all rows as not seem for next columns seen = zeros(1,N) ; seen (:) = 0;

% Find if the row 'u' can match a column [z , matchR] = bpm(A, u, seen, matchR); if (z)

result=result+l;

end

end

% Return maximum matching

35

у = result ; return

end

10

Листинг A.4 Код Matlab, bpm.m, для алгоритма Форда-Фулкерсона

function [z , matchR] = bpm(A , u, seen, matchR) [M,N] = size(A) ;

% Try every column one by one for v=l:N

if (A(u,v) && (~ seen(v)))

% mark columns 'v' visited seen(v)- 1;

if ( (matchR(v) <0) ) matchR(v)=u; z = 1; return

end

[z, matchR] = bpm(A,matchR(v), seen, matchR); if (z)

matchR(v)=u; z = 1; return

end

end

end

z = 0;

return

end

15

20

25

Приложение Б Результаты работы с таблицами

Б.1 Код С[5 х 7,3 • 7, 3]

С помощью компьютера результат кода С[5 х 7,3 • 7, 3] получен из таблицы 9:

Таблица 9 — Результат вычисления граничных рангов всех сопровождающих матриц

/0/1/2/3/4/5/6 Р(Сз,Column)

0 1 2 3 4 5

0000000 1 16 380 9712 169255 1917788

0000001 1 16 556 11335 161661 1923583

0000010 1 16 580 9758 155049 1931748

0000011 1 16 339 7347 153231 1936218

0000100 1 16 359 9147 150841 1936788

0000101 1 16 225 6829 147768 1942313

0000110 1 16 225 6802 147647 1942461

0000111 1 16 402 8716 146432 1941585

0001000 1 16 215 8121 151769 1937030

0001001 1 16 117 5805 146633 1944580

0001010 1 16 115 5845 146733 1944442

0001011 1 16 176 7570 140937 1948452

0001100 1 16 112 5764 146733 1944526

0001101 1 16 222 7724 142268 1946921

0001110 1 16 176 7569 140985 1948405

0001111 1 16 112 5631 143870 1947522

0010000 1 12 85 5654 158112 1933288

0010001 1 12 63 4477 152197 1940402

0010010 1 12 57 4291 149910 1942881

0010011 1 12 105 5163 147907 1943964

0010100 1 12 61 4310 149732 1943036

0010101 1 12 83 4990 145047 1947019

0010110 1 12 106 5110 144988 1946935

0010111 1 12 51 4023 145326 1947739

0011000 1 12 60 4478 152789 1939812

0011001 1 12 106 5392 148859 1942782

0011010 1 12 84 5037 145044 1946974

0011011 1 12 51 4024 145343 1947721

0011100 1 12 103 5139 147889 1944008

0011101 1 12 51 4011 145148 1947929

0011110 1 12 51 4023 145175 1947890

0011111 1 12 93 5208 145165 1946673

0100000 1 7 31 3707 127673 1965733

0100001 1 7 8 2943 123488 1970705

0100010 1 7 12 3022 123702 1970408

0100011 1 7 12 3322 121416 1972394

0100100 1 7 14 2996 123286 1970848

0100101 1 7 26 3375 121721 1972022

0100110 1 7 12 3311 121322 1972499

0100111 1 7 2 2773 119024 1975345

0101000 1 7 7 3084 123619 1970434

0101001 1 7 21 3506 121952 1971665

0101010 1 7 31 3517 122218 1971378

0101011 1 7 0 2743 119038 1975363

0101100 1 7 12 3319 121459 1972354

0101101 1 7 4 2766 119060 1975314

0101110 1 7 0 2742 119275 1975127

0101111 1 7 20 3157 117622 1976345

0110000 1 7 0 2985 123572 1970587

0110001 1 7 24 3511 122582 1971027

0110010 1 7 24 3473 121798 1971849

0110011 1 7 0 2744 119031 1975369

0110100 1 7 28 3367 121669 1972080

0110101 1 7 0 2752 119361 1975031

0110110 1 7 0 2753 119069 1975322

0110111 1 7 16 3221 117743 1976164

0111000 1 7 12 3314 121381 1972437

0111001 1 7 1 2759 118959 1975425

0111010 1 7 0 2740 119100 1975304

0111011 1 7 27 3221 117885 1976011

0111100 1 7 0 2766 119148 1975230

0111101 1 7 16 3222 117794 1976112

0111110 1 7 20 3125 117776 1976223

0111111 1 7 0 2575 116505 1978064

1000000 1 0 3 1788 91819 2003541

1000001 1 0 0 1677 91524 2003950

1000010 1 0 0 1679 91576 2003896

1000011 1 0 5 1821 91916 2003409

1000100 1 0 0 1675 91499 2003977

1000101 1 0 5 1833 91910 2003403

1000110 1 0 7 1824 92014 2003306

1000111 1 0 0 1671 91564 2003916

1001000 1 0 0 1678 91412 2004061

1001001 1 0 5 1847 92065 2003234

1001010 1 0 4 1829 91951 2003367

1001011 1 0 3 1722 91505 2003921

1001100 1 0 10 1829 91913 2003399

1001101 1 0 0 1696 91416 2004039

1001110 1 0 0 1684 91431 2004036

1001111 1 0 3 1817 92023 2003308

1010000 1 0 0 1681 91604 2003866

1010001 1 0 3 1888 92483 2002777

1010010 1 0 7 1906 92607 2002631

1010011 1 0 0 1692 91563 2003896

1010100 1 0 3 1819 91985 2003344

1010101 1 0 0 1686 91534 2003931

1010110 1 0 0 1685 91480 2003986

1010111 1 0 13 1868 92316 2002954

1011000 1 0 6 1824 92020 2003301

1011001 1 0 0 1679 91553 2003919

1011010 1 0 0 1685 91422 2004044

1011011 1 0 3 1830 91985 2003333

1011100 1 0 0 1673 91513 2003965

1011101 1 0 13 1845 92168 2003125

1011110 1 0 5 1856 92135 2003155

1011111 1 0 0 1670 91464 2004017

1100000 1 0 0 1669 91440 2004042

1100001 1 0 16 1968 92642 2002525

1100010 1 0 7 1871 92377 2002896

1100011 1 0 2 1658 91473 2004018

1100100 1 0 7 1850 92072 2003222

1100101 1 0 0 1680 91496 2003975

1100110 1 0 2 1683 91430 2004036

1100111 1 0 11 1896 92320 2002924

1101000 1 0 6 1828 91858 2003459

1101001 1 0 0 1681 91484 2003986

1101010 1 0 0 1694 91404 2004053

1101011 1 0 7 1840 92060 2003244

1101100 1 0 0 1686 91479 2003986

1101101 1 0 13 1867 92336 2002935

1101110 1 0 11 1851 92139 2003150

1101111 1 0 2 1694 91652 2003803

1110000 1 0 5 1814 91897 2003435

1110001 1 0 0 1677 91448 2004026

1110010 1 0 0 1687 91428 2004036

1110011 1 0 7 1905 92318 2002921

1110100 1 0 6 1700 91555 2003890

1110101 1 0 5 1863 92059 2003224

1110110 1 0 7 1821 91972 2003351

1110111 1 0 0 1664 91465 2004022

1111000 1 0 0 1699 91405 2004047

1111001 1 0 10 1909 92274 2002958

1111010 1 0 13 1877 92195 2003066

1111011 1 0 0 1675 91435 2004041

1111100 1 0 3 1832 91901 2003415

1111101 1 0 1 1713 91573 2003864

1111110 1 0 0 1675 91419 2004057

1111111 1 0 13 1881 92077 2003180