Исследование методов оптимизации нагрузки восстановления распределенных систем хранения данных на базе корректирующих кодов тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Климов Роман Владимирович

• Климов Роман Владимирович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Климов Роман Владимирович

ССОДЕРЖАНИЕ

ВВЕДЕНИЕ

Актуальность темы

Степень разработанности темы исследования

Цели и задачи исследования

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

Научная новизна диссертационного исследования

Теоретическая и практическая значимость работы

Внедрение результатов работы

Личный вклад

Апробация работы

Публикации

Краткое содержание работы

ГЛАВА 1. АНАЛИЗ СХЕМ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ В СОВРЕМЕННЫХ СИСТЕМАХ ХРАНЕНИЯ ДАННЫХ

1.1. Классификация методов организации хранения цифровой информации

1.2. Концепция фрагментарной обработки данных

1.3. Классификация событий повреждения массива данных и оценка статистических сведений об отказах хранилищ

1.4. Применение методов избыточного кодирования для восстановления поврежденных данных

1.5. Анализ существующих подходов к реализации распределенного хранения данных и выявление их достоинств и недостатков

1.5.1. Массив устройств хранения без отказоустойчивости (RAID 0)

1.5.2. Массив устройств хранения данных с кодами повторениями

1.5.3. Массив устройств хранения данных с кодами Хемминга

1.5.4. Массив устройств хранения данных с простой проверкой на

четность

1.5.5. Массив устройств хранения данных с кодами Рида-Соломона

1.6 Выводы к главе и постановка задач на исследования

ГЛАВА 2. МОДЕЛИРОВАНИЕ НАДЕЖНОСТИ СИСТЕМ ХРАНЕНИЯ ДАННЫХ

2.1. Постановка задачи

2.2. Критерий используемых ресурсов памяти

2.3. Критерий внутрисетевой нагрузки восстановления

2.4. Критерии надежности СХД

2.4. Выводы по главе

ГЛАВА 3. СНИЖЕНИЕ ВНУТРИСЕТЕВОЙ НАГРУЗКИ НА БАЗЕ

ПРИМЕНЕНИЯ РЕГЕНЕРАЦИОННЫХ КОДОВ

3.1 Постановка задачи

3.2. Концептуальные основы построения регенеративных кодов

3.3. Обобщенная схема построения регенерационных кодов

3.4 Процедура построения регенерационного кода-произведения с

простой проверкой на четность с регулярным смещением

3.5. Процедура реконструкции содержимого утраченного устройства хранения данных

3.6 Процедура обнаружения и коррекции одиночных ошибок ввода

вывода

3.7. Выводы по главе

ГЛАВА 4. ОПТИМИЗАЦИЯ ВНУТРИСЕТЕВОЙ НАГРУЗКИ НА БАЗЕ

ЛОКАЛЬНО ДЕКОДИРУЕМЫХ КОДОВ

4.1 Постановка задачи

4.2. Концептуальная основа построения ЛД- кодов

4.3 Обобщенная схема построения ЛД-кодов

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

размерности

4.5. Особенности образования некорректируемых ошибок в коде-произведении с простой проверкой на четность

4.6. Построение квазилокальных кодов на базе МДР-кодов

4.7. Применение перестановочного декодирования при восстановлении содержимого СХД с квазилокально-декодируемыми кодами

4.8. Выводы к главе

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Исследование методов оптимизации нагрузки восстановления распределенных систем хранения данных на базе корректирующих кодов»

Актуальность темы

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

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

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

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

новоприбывших накопителей. Наибольшую актуальность данная проблема приобретает в РСХД со значительным разнесением узлов.

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

Степень разработанности темы исследования

Методы регенерационного кодирования, применяемого в целях снижения нагрузки на сеть хранения данных разрабатывались Alexandras G. Dimakis, Kannan R. В работах авторов описаны концептуальные основы построения регенерационных кодов (РК). Вместе с этим описанные решения базируются на применении кодов Рида-Соломона со сложными схемами перемежения между кодовыми словами, что повышает сложность реализации системы хранения данных.

Задачи локального-декодирования кодов (ЛДК) решались Сергеем Еханиным, Parikshit Gopalan, Cheng Huang, Uuseyin Simitci. Авторами описывались основные подходы к осуществлению построения ЛДК для систем распределенного хранения данных.

Вопросы надежности распределенных систем хранения данных решались Рахманом П.А., Иваничкиной Л.В., Непорада А.П., Kevin M, James S. Plank, Jay J. Wyle, K.Gopinath. В работах авторов описаны методы вероятностей отказов УХД, входящих в состав СХД, и полной утраты информационного массива размещенного в ней. Недостатком описанных подходов является использование замкнутых цепей Маркова, не позволяющих прогнозировать состояния в системах с динамически изменяемыми интенсивностями отказов УХД.

Цели и задачи исследования

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

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

1. Выполняется анализ существующих подходов к организации СХД, базирующихся на методах помехоустойчивого кодирования, выявляются их достоинства и недостатки.

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

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

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

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

Объект исследования: системы хранения данных, включая распределенные системы их хранения.

Предмет исследования: системы хранения данных и методы их восстановления с использованием аппарата избыточных кодов.

Результат исследования соответствует пункту 2, 3, 9 и 12 паспорта научной специальности 05.12.13 - Системы, сети и устройства телекоммуникаций.

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

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

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

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

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

5. Метод квазилокального декодирования МДР-кодов с использованием аппарата перестановочного декодирования, учитывающий топологическое расположение накопителей в сети СХД.

Научная новизна диссертационного исследования

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

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

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

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

Теоретическая и практическая значимость работы

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

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

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

Внедрение результатов работы

Результаты исследования внедрены в организации ФНПЦ АО «НПО «Марс» г. Ульяновск при выполнении НИР «Разработка комплексных методов оценки динамически изменяющихся параметров корабельной компьютерной сети и алгоритма работы коммутатора Ethernet» Шифр - «СЕТЬ -1Е УлГТУ» завершенной в 2016 году и составной части ОКР «Создание телекоммуникационной сети ИСБУ» Шифр - «УлГТУ - ТКС», проведенной ФНПЦ АО «НПО «Марс»» совместно с Ульяновским государственным техническим университетом и завершенной в 2017 году, а также в учебный процесс УлГТУ, что подтверждается соответствующими актами.

Личный вклад

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

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

Апробация работы

Результаты диссертации докладывались и обсуждались на следующих конференциях: Научная сессия РНТОРЭС им. Попова, посвященная Дню Радио, г. Москва (2013, 2014); Международная конференция «Цифровая обработка сигналов и ее применение» - DSPA, г. Москва (2014, 2015); Международная научно-техническая конференция «Радиолокация, навигация, связь» - RLNC, г. Воронеж (2013, 2014, 2016, 2017); Международная научно-техническая конференция «Проблемы техники и технологий телекоммуникаций» - ПТиТТ, г. Казань (2014, 2017); Международная научно-техническая конференция «Проблемы техники и технологий телекоммуникаций» - ПТиТТ, г. Самара (2016); Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем», г. Ульяновск (2014, 2015, 2017).

Публикации

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

Краткое содержание работы

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

новизна, и практическая значимость полученных результатов, сформулированы основные положения, выносимые на защиту.

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

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

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

В четвертой главе представлено описание построения и применения ЛД кодов. Описаны основные требования к осуществлению локального декодирования. Представлен новый подход к осуществлению квазилокальному декодированию МДР-кодов.

ГЛАВА 1. АНАЛИЗ СХЕМ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ В СОВРЕМЕННЫХ СИСТЕМАХ ХРАНЕНИЯ ДАННЫХ

1.1. Классификация методов организации хранения цифровой

информации

Процесс хранения данных непосредственно связан с понятиями носителя информации (материального объекта, фиксирующего в своей структуре занесенную в него информацию) и УХД или накопителя (устройства, содержащего носитель информации и предназначенного для осуществления хранения данных) [16]. К наиболее значимым свойствам УХД относятся: объем хранимых данных, обеспечиваемая надежность хранения, доступность информации, размещенной в накопителе.

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

- разработка новых информационных носителей и накопителей на их основе;

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

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

УХД.

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

ферромагнетика, подвергнутых ранее воздействию магнитного поля; твердотельные - основаны на способности транзисторов с плавающим затвором, накапливать и сохранять в течении долгого времени электрические заряды [17,54,55,61,66,84,85,86]. Обобщенная классификация УХД, по физическим явлениям, лежащим в основе их функционирования, представлена на рисунке. 1.1.

Рисунок 1.1. - Классификация УХД.

УХД, базирующиеся на оптических эффектах (перфокарты, перфоленты, оптические диски различной природы, магнитооптические диски) обладают высоким сроком сохранения работоспособности (20 - 100 лет для оптических дисков, вплоть до деградации отражающего слоя). Подобные накопители предназначены для малого числа перезаписей, что не позволяет применять их для хранения динамически изменяемых данных. Недостатками данной разновидности УХД является низкая устойчивость к механическим и температурным повреждениям, малый объем хранимой информации по сравнению с накопителями, основанными на других физических принципах, а так же малая скорость доступа к данным (операции ввода-вывода, и перезаписи данных), что вызвано применением последовательного доступа к данным.

Накопители, основанные на принципе сохранения остаточной

намагниченности, позволяют организовывать хранение наибольшего объема данных. Кроме того накопители на жестких магнитных дисках (НЖМД) обладают

14

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

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

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

Организация долговременного хранения данных только на базе применения отдельных УХД обладает рядом фундаментальных ограничений:

- невозможно обеспечить хранение сколь либо большого объема данных;

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

- небольшая надежность отдельных УХД и их подверженность влиянию внешних деструктивных факторов не позволяет обеспечивать гарантированного долгосрочное хранения.

Для решения вышеобозначенных проблем возможно УХД в СХД. Применение РСХД направлено на три основных цели: увеличить объем, доступный для размещения информации; повысить быстродействие систем хранения и обработки информации; увеличить надежность долгосрочного хранения данных. Концептуально подход РСХД базируется на применении аппарата виртуализации хранения данных, и в частности массивов УХД.

Массив устройств хранения данных (RAID) - СХД, представляющая собой набор физических запоминающих устройств, управляемых операционной системой или специализированными контроллерами. Массивы воспринимаются внешними вычислительными системами как единое пространство для размещения и хранения данных. Фрагменты данных, размещаемых в RAID, распределяются в памяти отдельных накопителей, входящих в состав массива.

За счет применения концептуальных основ RAID, РСХД являются крайне гибкими к построению больших хранилищ данных. Масштабирование СХД осуществляется простым подключением новых УХД. Таким образом, объем системы хранения может неограниченно увеличиваться.

1.2. Концепция фрагментарной обработки данных

Базовым принципом построения УХД и СХД является представление информации в форме данных и их организация в форме отдельных фрагментов.

Концепция фрагментарного хранения данных заключается в том, что исходный массив данных D размера М символов подвергается разделению на множество М1 = {т | т еМ,i = 1 ...к} независимых фрагментов равного размера

I < Мк [53,75]. Полученные в результате фрагменты являются независимыми, то

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

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

к-1

м = и М1, (1.1)

I = 0

М = М1|| М2 к || М1, (1.2)

dJ с Мг, dj с М] ^ dI I dj = 0 , (1.3)

где М1 || М1+1 - присоединение цепью фрагментов М1, Mj е М, dI и dj -элементы фрагментов М1 и М j.

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

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

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

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

1.3. Классификация событий повреждения массива данных и оценка статистических сведений об отказах хранилищ.

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

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

- события утраты отдельных фрагментов или их групп, вызванных выходом из строя отдельных УХД.

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

Рис. 1.2. Классификация ошибок возникающих в ходе хранения данных

Возникновение событий утраты аутентичности данных может быть вызвано:

- старением информационного носителя, что приводит к изменению его свойств (изменение отражающей способности оптических покрытий, спонтанное изменение направления вектора намагниченности отдельных доменов ферромагнетика в НЖМД);

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

- возникновения битовых ошибок на этапе их подготовки к записи в накопитель и до их фиксации носителем данных.

Характер подобных событий, выраженный в локальности искажений и малом числе ошибок на фрагмент, что в случае событий старения или возникновения микро- и макроповреждений носителя, позволяет производить исправление ошибок встроенными средствами УХД, такими как применение интерполяции и простых схем помехоустойчивого кодирования [21].

Особый характер носят ошибки ввода-вывода, возникающие в процессе передачи данных от источника информации к накопителю. Они фиксируются УХД как аутентичные данные, и подвергаются обработке наряду с неискаженными. Эти ошибки не могут быть обнаружены и скорректированы накопителем, и могут быть исправлены только на уровне дисковых массивов или РСХД. В то же время данные события носят характер истинных ошибок с неопределенным местом дислокации, что дополнительно усложняет задачу реконструкции необходимостью определения их местоположения. Для борьбы с данными видами ошибок имеется широкий арсенал средств повышения как надежности функционирования программно-аппаратных средств источника информации и УХД, так и достоверности передаваемой информации. Последнее достигается путем широкого распространения волоконно-оптических линий связи, а так же различных методов помехоустойчивого кодирования и применения методов мягкого декодирования [7,13,24,25,36]. Последнее позволяет

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

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

Список литературы диссертационного исследования кандидат наук Климов Роман Владимирович, 2018 год

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Айвазян С. А., Прикладная статистика: Основы моделирования и первичная обработка данных. Справочное изд. / С. А. Айвазян, И. С. Енюков, Л. Д. Мешалкин. — М.: Финансы и статистика, 1983. — 471 с.

2. Вентцель Е. С., Исследование операций. / Вентцель Е. С. // М., «Советское радио», 1972, - 552 с.

3. Вентцель Е. С., Исследование операций: задачи, принципы, методология. / Вентцель Е. С. // 2-е изд., стер.— М.: Наука. Гл. ред. физ.-мат. лит., 1988,— 208 с.

4. Вологдин Э.И., Цифровая звукозапись / Вологдин Э.И. // Санкт-Петербург, 2012, - 136 с.

5. Галлагер Р., Теория информации и надежная связь. / Галлагер Р.// Перев. с англ. под ред. М. С. Пинскера и Б. С. Цыбакова. М., «Сов. радио», 1974. -720 с.

6. Ганин Д.В., Особенности моделирования надежности распределенных систем хранения данных / Ганин Д.В., Климов Р.В. // Вестник НГИЭИ. 2017. № 7 (74). - стр. 18-25.

7. Гладких А.А. / Метод формирования индексов мягких решений в системе с квадратурно-амплитудной модуляцией // Гладких А.А., Климов Р. В., Линьков И.С. // DSPA-2013. Международная конференция Цифровая обработка сигналов и её применение. 2013

8. Гладких А.А. Метод эффективного декодирования избыточных кодов и их приложения / Гладких А.А., Климов Р.В., Чилихин Н.Ю. // Ульяновск : УлГТУ, 2016. - 258 с.

9. Гладких А.А., Основы теории мягкого декодирования избыточных кодов в стирающем канале связи / Гладких А.А. // Ульяновск : УлГТУ, 2010 - 379 с.

10. Гладких А.А., Перестановочное декодирование как инструмент повышения энергетической эффективности систем обмена данными / Гладких А.А. // Электросвязь. - 2017 №8. - стр. 52 - 56.

11. Гладких А.А., Система быстрых матричных преобразований в процедуре формирования эквивалентных избыточных кодов. / Гладких А.А., Ал Тамими Т.Ф.Х. //Радиотехника. - 2017. - № 6. - стр. 41 - 44.

12. Гладких А.А., Адаптивный кодер гиперкода размерности 3D. / Гладких А.А., Капустин Д.А., Климов Р.В., Солодовникова Д.Н. // Патент на изобретение №2480918, опубликовано: 27.04.2013 Бюл. № 12.

13. Гладких А.А., Численное моделирование обобщенной процедуры формирования индексов мягких решений / Гладких А.А., Климов Р.В. // Инфокоммуникационные технологии. 2013. Т. 11. № 2. - стр. 22-28.

14. Гладких А.А., Методы снижения внутрисетевой нагрузки в распределенных системах хранения / Гладких А.А., Климов Р.В., Сорокин И.А. // Автоматизация процессов управления. 2015. № 3 (41). - стр. 34-40.

15. Гладких А.А., Унификация процедуры обработки данных в информационно-управляющих комплексах на базе полярных кодов / Гладких А.А., Климов Р.В., Чилихин Н.Ю. // В сборнике: Радиолокация, навигация, связь XXI Международная научно-техническая конференция. 2015. - стр. 1021-1031.

16. ГОСТ 34.321-96. Информационные технологии. Система стандартов по базам данных. Эталонная модель управления данными.

17. Гук, М. Дисковая подсистема ПК /М. Гук// СПб.: Питер, 2001. - 336 с.

18. Дворкович А.В., Дворкович В.П. Цифровые видеоинформационные системы (теория и практика) / Дворкович А.В., Дворкович В.П. //Москва: Техносфера, 2012. — 1009 с.

19. Диллон Б., Инженерные методы обеспечения надежности систем / Диллон Б., Сингх Ч. // Пер. Е.Г. Коваленко, М.:"МИР", 1984, - 320 с.

20. Иваничкина Л.В., Модель надежности распределенной системы хранения данных в условиях явных и скрытых дисковых сбоев / Иваничкина Л.В., Непорада А.П. // Труды ИСП РАН, том 27, вып. 6, 2015 г. - стр. 253-274.

21. Касперски К., Восстановление данных. Практическое руководство /К. Касперсикй // СПб.: БХВ-Петербург. 2007. - 352 с.

22. Кларк Дж., Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. / Кларк Дж., мл., Кейн Дж.// М.: Радио и связь, 1987. — 392 с.

23. Климов Р.В. / Обобщенная процедура сокращения внутрисетевого трафика в системах распределенного хранения на основе регенерационных кодов // Климов Р.В. //17-я Международная конференция Цифровая обработка сигналов и ее применение. 2015.

24. Климов Р.В. / Разработка процедуры формирования индексов мягких решений принятых символов с расширенной зоной стираний // Климов Р.В. //16-я Международная конференция Цифровая обработка сигналов и ее применение. 2014.

25. Климов Р.В., Исследование процесса формирования индексов мягких решений со сниженным числом ложных стираний / Климов Р.В. // REDS: Телекоммуникационные устройства и системы. 2014. Т. 4. № 2. - стр. 101-105.

26. Климов Р.В., Методы оценки надежности систем хранения данных / Климов Р.В. // материалы XVIII Международной научно-технической конференции. Казань, 20 -24 ноября 2017 года. - Казань: КНИТУ-КАИ, 2017. - Т. 1. - стр. 219 -220.

27. Климов Р.В. Методы снижения внутрисетевого трафика в процедуре восстановления данных // Радиотехника №9 - 2016 г. - стр. 44-47.

28. Климов Р.В., Модель надежности систем хранения данных в условиях утраты и восстановления хранилищ / Климов Р.В. // Современные проблемы проектирования, производства и эксплуатации радиотехнических систем. 2017. № 1-2 (10). - стр. 195-198.

29. Климов Р.В., Обзор программных методов обеспечения надежности хранения информации в распределенных системах хранения информации / Климов Р.В. // Современные проблемы проектирования, производства и эксплуатации радиотехнических систем. 2015. № 1-2 (9). - стр. 148-150.

30. Климов Р.В., Осуществление регенерационного кодирования на базе кодов-произведений с простой проверкой на четность / Климов Р.В. // Вестник НГИЭИ. 2018. № 3 (82). - стр. 18-25.

31. Климов Р.В., Подход к модификации модели оценки надежности распределенных систем хранения данных / Климов Р.В. // материалы XVII Международной научно-технической конференции. 22 -24 ноября 2016 года. -Самара: ПГУТИ 2016. - Т. 1. - стр. 199 -200.

32. Климов Р.В., Применение комплекса сетевого и помехоустойчивого кодирования в системах распределенного хранения / Климов Р.В. // В сборнике: Проблемы техники и технологий телекоммуникаций ПТиТТ-2014; Оптические технологии в телекоммуникациях 0ТТ-2014 Материалы Международных научно-технических конференций. 2014. - стр. 105-107.

33. Климов Р.В., Совместное применение сетевого и помехоустойчивого кодирования в системах распределенного хранения данных / Климов Р.В. // Современные проблемы проектирования, производства и эксплуатации радиотехнических систем. 2014. № 1 (9). - стр. 82-85.

34. Климов Р.В., Применение дополненного аппарата регенерационного кодирования для оптимизации внутрисетевого трафика / Климов Р.В., Пчелин Н.А., Тамразян Г.М.// REDS Телекоммуникационные устройства и системы. 2015. Т. 5. № 1. - стр. 115-118.

35. Климов Р.В., Особенности моделирования процессов отказов устройств хранения в распределенных системах хранения данных / Климов Р.В., Соловьева М.С.// В сборнике: радиолокация, навигация, связь XXII международная научно-техническая конференция. Воронеж, 2017. - стр. 179-184.

36. Климов Р.В., Модель формирования индексов мягких решений символов на основе модификации параметров канала со стираниями / Климов Р.В., Солодовникова Д.Н. // Радиотехника. 2014. № 11. - стр. 90-93.

37. Климов Р.В., Оптимизация трафика восстановления узлов распределенных систем хранения данных / Климов Р.В., Чилихин Н.Ю.// В

сборнике: радиолокация, навигация, связь XXII международная научно-техническая конференция. Воронеж, 2016. - стр. 671-681.

38. Конопелько В.К., Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов. / Конопелько В.К., Липницкий В.К. // М. : Едиториал УРСС, 2004. - 176 с.

39. Локшин М.В., Исследование надежности RAID-0 массивов в системах с репликацией данных / Локшин М.В. // Вестник воронежского государственного технического университета, 2013, Том: 9, №6-3. - стр. 93-97.

40. Лысов А. А., Распределенные системы хранения данных: анализ, классификация и выбор / Лысов А. А., Мазур Э. М., Тормасов А. Г. // Труды Института системного программирования РАН - Москва, 2015 - том 27. выпуск 6

- стр. 225 - 252.

41. Морелос-Сарагоса Р., Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса.// - М.: Техносфера, 2005.

- 320 с.

42. Ногин В.Д., Принятие решений в многокритериальной среде. Количественный подход / Ногин В.Д.// М.: ФИЗМАТЛИТ, 2005. - 176 с.

43. Питерсон У., Коды, исправляющие ошибки / Питерсон У., Уэлдон Э.//Пер. с англ. под ред. Р.Л. Добрушина и С.Н. Самойленко. - М.: Мир, 1976. -594 с.

44. Поляков А.,Тестирование производительности дискового массива SATA RAID / Поляков А. // [Электронный ресурс] // https://www.ferra.ru/ru/system/s25425/ (дата доступа: 08.01.2018)

45. Рахман П.А., Модель надежности дисковых массивов RAID-5 с одинарной избыточностью / Рахман П.А. // Актуальные проблемы гуманитарных и естественных наук, М, 2015, №8-1. - стр. 55-57.

46. Рахман П.А., Модель надежности каскадных дисковых массивов RAID-10 с чередованием и зеркалированием данных / Рахман П.А. // Актуальные проблемы гуманитарных и естественных наук, М, 2015, №8-1. - стр. 60-63.

47. Рахман П.А., Марковские модели надежности каскадных дисковых массивов RAID-01 И RAID-10 / Рахман П.А., Муравьева У.А. // Вестник молодого ученого УГНТУ, Уфа, 2015, №1. - стр. 52-60.

48. Рахман П.А., Модель надежности дисковых массивов RAID-6 с двойной избыточностью / Рахман П.А. // Актуальные проблемы гуманитарных и естественных наук, М, 2015, №8-1. - стр. 57-60.

49. Рахман П.А., Модель надежности каскадных дисковых массивов RAID-01 с зеркалированием и чередованием данных / Рахман П.А. // Актуальные проблемы гуманитарных и естественных наук, М, 2015, №8-1, стр. 63-66.

50. Рост объема информации - реалии цифровой вселенной// ТЕХНОЛОГИИ И СРЕДСТВА СВЯЗИ № 1 (94) 2013. - стр. 24-25.

51. Семеренко В. П. Теория и практика CRC кодов: новые результаты на основе автоматных моделей / Семеренко В. П. // Восточно-Европейский журнал передовых технологий. 2015. № 4/9. стр. 38— 48.

52. Скляр, Б. Цифровая связь. Теоретические основы и практическое применение / Бернард Скляр // Изд. 2-е, испр. пер. с англ. - М.: Издательский дом «Вильямс», 2003. - 1104 с.

53. Соколинский Л.Б., Параллельные системы баз данных: Учебное пособие. / Соколинский Л.Б.// М.: Издательство Московского университета, 2013. - 184 с.

54. Чепурной В., Устройства хранения информации / В. Чепурной // СПб.: BHV-Санкт-Петербург, 1998. - 208с.

55. Шарапов Р.В. Аппаратные средства хранения больших объемов данных / Шарапов Р.В. // Инженерный вестник Дона, 2012, Т. 24, №4-2 (23).

56. Шубин Р.А. Надежность технологических систем и техногенный риск / Шубин Р.А. // Тамбов, Издательство ФГБОУ ВПО «ТГТУ», 2012. - С. 80.

57. Abraham Silberschatz, Operating System Concepts / Abraham Silberschatz, Peter B. Galvin, Greg Gagne// John Wiley & Sons, Ink., 2013, 976 pages.

58. Andy Klein, Hard Drive Stats for Q1 2017 / Andy Klein // [Электронный ресурс] URL: https://www.backblaze.com/blog/hard-drive-failure-rates-q1-2017.

59. Beach, B. What Hard Drive Should I Buy? / Beach, B.// [Электронный ресурс] URL: https://www.backblaze.com/blog/what-hard-drive-should-i-buy.

60. Bianca Schroeder, Disk failures in the real world:What does an MTTF of 1,000,000 hours mean to you?/ Bianca Schroeder, Garth A. Gibson// FAST '07 Proceedings of the 5th USENIX conference on File and Storage Technologies.

61. Blu-ray Disc Format. White paper. [Электронный ресурс] // URL: www.blurayjukebox.com/ generalbluraydiscformat-12834 .pdf.

62. Brouwer P., The art of data replication / Brouwer P. // An Oracle Technical White Paper, Oracle Corporation World Headquarters 500 Oracle Parkway Redwood Shores, 2011. - pp. 1-28.

63. Cole G., Estimating drive reliability in desktop computers and consumer electronics systems. / Cole G.// TP- 338.1. Seagate. 2000.

64. Dimakis A., Network coding for distributed storage systems / Dimakis A., Godfrey P., Wu Y., Wainwright M., Ramchandran K. // Information Theory, IEEE Transactions on, vol. 56, № 9,2010. - pp. 4539-4551,

65. Eduardo Pinheiro, Failure Trends in a Large Disk Drive Population / Eduardo Pinheiro, Wolf-Dietrich Weber, Luiz Andre Barroso // 5th USENIX Conference on File and Storage Technologies (FAST 2007). - pp. 17-29.

66. Flash Memory Technology. // [Электронный ресурс] URL: http ://smithsonianchips. si.edu/ice/cd/MEMORY97/SEC 10 .PDF.

67. Gopalan P., On the Locality of Codeword Symbols / Gopalan P., Huang C., Simitci H., Yekhanin S.// IEEE Transactions on Information Theory, 2012, Volume: 58, Issue: 11, pp. 6925 - 6934.

68. Greenan K.M., Mean Time To Meaningless: MTTDL,Markov models, and Storage System Reliability / Greenan K.M., Plank J.S., Wylie J.J. // Proceedings of the 2nd USENIX conference on Hot topics in storage and file systems, 2010. - pp. 1-5.

69. Hanxu Hou, Rack-Aware Regenerating Codes for Data Centers / Hanxu Hou, Patrick P. C. Lee, Kenneth W. Shum, Yuchong Hu // URL:https://arxiv.org/pdf/1802.04031 .pdf (Дата обращения: 13.02.2018)

70. Huang C., Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems / Huang C., Chen M., Li J. // Sixth IEEE International Symposium on Network Computing and Applications, 2007.

71. IDC digital universe 2014 Russia // URL: https://russia.emc.com/collateral/analyst-reports/idc-digital-universe-2014-russia.pdf (дата обращения: 25.05.2017).

72. James S. Plank, A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems / James S. Plank // Software—Practice & Experience, Volume 27 Issue 9, 1997. - pp 995 - 1012.

73. Jy-yong Sohn, A Class of MSR Codes for Clustered Distributed Storage / Jy-yong Sohn, Beongjun Choi, Jaekyun Moon // URL: https://arxiv.org/pdf/1801.02014.pdf (Дата обращения: 05.03.2018).

74. Karmakar P., Are Markov Models Effective for Storage Reliability Modelling? / Karmakar P., Gopinath K. // URL: https://arxiv.org/pdf/1503.07931.pdf (Дата обращения: 27.05.2017).

75. Katarzyna Kapusta, Data protection by means of fragmentation in various different distributed storage systems - a survey / Katarzyna Kapusta, Gerard Memmi // URL: https://arxiv.org/pdf/1706.05960.pdf.

76. Kryder M. H. Gage, Heat Assisted Magnetic Recording / Kryder M. H. Gage, E. C., McDaniel T. W., Challener W. A., RottmayerR. E., Ju G., Hsia Y.-T., Erden M. F.// Proc. IEEE, vol. 96, no. 11, 2008. - pp. 1810-1835.

77. Marwen Zorgui On the Achievability Region of Regenerating Codes for Multiple Erasures / Marwen Zorgui, Zhiying Wang // URL:https://arxiv.org/pdf/1802.00104.pdf (Дата обращения: 06.03.2018).

78. Mazulu M.C. Database Replication // Database Systems Journal, 2010, vol. I, № 2. - p. 33 - 38.

79. Pasalic E., Coding Theory and Applications Solved Exercises and Problems of Linear Codes / Pasalic E. // Fakulteta za matematiko, naravoslovje in informacijske tehnologije, 2013. - 34 pages.

80. Patterson D. A., A Case for Redundant Arrays of Inexpensive Disks (RAID) / Patterson D. A. , Gibson G. , KatzR. H. // Proc. of ACM SIGMOD, 1988.

81. Rashmi K. V., Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction / Rashmi K. V., Nihar B. Shah, Vijay Kumar P. // IEEE Transactions on vol. 57, № 8, 2011. - pp. 5227-5239.

82. Ross N. Williams, A painless guide to CRC error detection algorithms / Ross N. Williams // [Электронный ресурс] URL: http://www.ross.net/crc/download/crc_v3.txt.

83. Shrivastava P., Error Detection and Correction Using Reed Solomon Codes / Shrivastava P., Uday Pratap Singh // International Journal of Advanced Research in Computer Science and Software Engineering, 2013, vol 3, Issue 8. - pp. 965 - 969.

84. Standard ECMA-267.120 mm DVD - Read-Only Disk. - Standardizing Information and Communication Systems, 2001.

85. Standard ECMA-316. 8 mm Wide Magnetic Tape Cartridge for Information Interchange - Helical Scan Recording - VXA-1 Format. - Standardizing Information and Communication Systems, 2001.

86. Standart ECMA-130. Data interchange on read-only 120 mm optical data disk (CD-ROM) - Standardizing Information and Communication Systems, 2001.

87. Steve Jiekak, Regenerating Codes: A System Perspective./ Steve Jiekak, Anne-Marie Kermarrec, Nicolas Le Scouarnec, Gilles Straub, Alexandre Van Kempen. // Dependability Issues in Cloud Computing (DISCCO 2012), 2012, Irvine. - pp.436441.

88. Yekhanin, S. Locally decodable codes / S. Yekhanin // 6th International Computer Science Symposium in Russia - 2011 - p. 289 - 290.

89. Yuchong Hu, Optimal Repair Layering for Erasure-Coded Data Centers: From Theory to Practice / Yuchong Hu, Xiaolu Li, Mi Zhang, Patrick P. C. Lee, Xiaoyang Zhang, Pan Zhou, Dan Feng // ACM Transactions on Storage 13(4), 2017.

ПРИЛОЖЕНИЕ А Адаптивный кодер гиперкода размерности 3D

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

Структурная схема адаптивного кодера гиперкода размерности 3D представлена на фиг. 1.

Адаптивный кодер гиперкода размерности 3D содержит буфер 1 входящей информации, выход которого подключен к входу блока 2 проверки четности ^ разрядной комбинации, при этом первый выход блока 2 проверки четности ^ разрядной комбинации соединен с входом счетчика-распределителя 3, а второй выход блока 2 проверки четности ^разрядной комбинации подключен к одноименному входу счетчика-распределителя 5 на ^+1) тактов, при этом ^+1) выход счетчика-распределителя 3 подключен к одноименным входам регистра 4 вертикальных проверок, при этом первый выход регистра 4 вертикальных проверок соединен с одним из входов блока 9 управления, тогда как второй выход

регистра 4 вертикальных проверок подключен к первому входу счетчика-

2 2

распределителя 5 на (к+1) тактов и (к+1) выходов счетчика-распределителя 5 на (к+1) тактов подключены к одноименным входам сумматора 6 проверок 3D, при этом в свою очередь (к+1) выходов сумматора 6 проверок 3D подключены к одноименным входам накопителя 7 проверок 3D, выход которого, объединенный с главным выходом счетчика-распределителя 5 на (к+1) тактов, подключен к прямому каналу связи, тогда как обратный канал связи подключен к входу блока 8 выделения запроса, первый вход которого соединен с управляющим входом накопителя 7 проверок 3D, а второй выход подключен к другому входу блока 9 управления, выход которого соединен с управляющим входом буфера 1 входящей информации.

Назначения отдельных блоков адаптивного кодера и их совместная работа рассматриваются на примере обработки комбинаций с к=3.

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

Блок 2 проверки четности к-разрядной комбинации предназначен для выполнения проверки четности в группе к двоичных символов, поступающих с выхода буфера 1 входящей информации. После выполнения процедуры проверки четности комбинация в (к+1) символ в последовательном коде поступает одновременно на первый и второй выходы блока 2 проверки четности к-разрядной комбинации. При этом первый выход подключен к входу счетчика-распределителя 3, а второй выход блока 2 проверки четности к-разрядной комбинации подключен ко второму входу счетчика-распределителя 5 на (к+1) тактов. Информация, передаваемая через второй выход блока 2 проверки четности к-разрядной комбинации без изменений и задержек, передается через блок 5 в прямой канал связи.

Счетчик-распределитель 3 предназначен для распределения значений (к+1) разрядной комбинации по (к+1) сумматорам, при передаче ровно (к+1)-й комбинаций сумматоры определяют четность информационных и проверочных символов на одноименных позициях этих комбинаций. Состояние сумматоров после обработки к комбинаций соответствует проверкам на четность по вертикали в традиционной системе двух кодов произведений. Для получения подобных проверок счетчик-распределитель 3 связан с регистром 4 вертикальных проверок ровно (к+1) выходами.

Регистр 4 вертикальных проверок предназначен для фиксации через каждые кх(к+1) тактов работы адаптивного кодера проверок четности по вертикали. Этот блок имеет 2 выхода. Первый выход предназначен для передачи сигнала управления в блок 9 управления, который блокирует выход буфера 1 входящей информации на (к+1) такт (режим 2). За время блокировки буфера 1 входящей информации регистр 4 вертикальных проверок через второй выход и первый вход счетчика-распределителя 5 на (к+1) тактов передает проверочные символы по вертикали в прямой канал связи.

Счетчик-распределитель 5 на (к+1) тактов предназначен для трансляции (к+1) разрядной комбинации, получаемой с первого или со второго входов через главный выход в прямой канал связи, а также для распределения значений этой

последовательности по (к+1) сумматорам. При передаче (к+1) комбинаций сумматоры определяют четность информационных и проверочных символов на одноименных позициях в этих комбинациях. Состояние сумматоров после обработки к комбинаций соответствует проверкам на четность размерности 3D в

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

2 2 на (к+1) тактов связан с сумматором 6 проверок 3D (к+1) параллельными

выходами.

Сумматор 6 проверок 3D предназначен для суммирования и фиксации по завершении к*(к+1) тактов работы кодера окончательного итога проверок четности размерности 3D. Этот блок имеет (к+1) выходов, занумерованных от 1 до (к+1) , подключенных к одноименным входам накопителя 7 проверок 3D. После сброса информации из сумматора 6 проверок 3D в накопитель 7 проверок 3D сумматор 6 проверок 3D готов к обработке очередной последовательности битов.

Накопитель 7 проверок 3D предназначен для хранения символов проверки размерности 3D и передачи их последовательным кодом в прямой канал связи только в случае поступления запроса по каналу обратной связи. Накопитель 7 проверок 3D имеет (к+1) входов и один управляющий вход. Управляющий вход подключен к первому выходу блока 8 выделения запроса. Выход накопителя 7 проверок 3D объединен с главным выходом счетчика-распределителя 5 на (к+1) тактов и подключен к прямому каналу связи. Если через установленное число тактов работы кодера после передачи кодового слова запроса на передачу дополнительной избыточности не поступило, накопитель 7 проверок 3D обнуляет накопитель проверок 3D, относящихся к переданному кодовому слову. Число установленных тактов работы кодера является переменным и зависит от параметров обратного канала связи. Процесс обнуления накопителя носит циклический характер.

Блок 8 выделения запроса предназначен для выделения комбинации запроса из канала обратной связи и управления передачей дополнительной избыточности из накопителя 7 проверок 3D в прямой канал связи. Данный блок имеет два

выхода. Второй выход предназначен для передачи сигнала управления в блок 9 управления, который блокирует выход буфера 1 входящей информации на (к+1) такт. В это же время управляющая команда передается по первому выходу на управляющий вход накопителя 7 проверки 3D, который за время блокировки буфера 1 входящей информации передает проверочные символы размерности 3D из накопителя 7 проверки 3D в прямой канал связи.

Блок 9 управления предназначен для управления последовательностями передаваемой информации. Данный блок имеет выход, подключенный к управляющему входу буфера 1 входящей информации. Блок 9 управления имеет два входа. Один из них подключен к первому выходу регистра 4 вертикальных проверок. При поступлении команды с этого выхода блок 9 управления блокирует выход буфера 1 входящей информации на (к+1) такт. Другой вход блока 9 управления подключен к второму выходу блока 8 выделения запроса. При поступлении управляющей команды с этого входа блок 9 управления блокирует выход буфера 1 входящей информации на (к+1) такт.

Работа адаптивного кодера гиперкода размерности 3D рассматривается на примере передачи информации при к=3.

На вход буфера 1 входящей информации от источника информации поступает некоторая последовательность двоичных символов вида:

...101 001 000 111 011 011 001 110 100...

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

... 0101 1001 0000 1111 0011 0011 1001 0110 1100/

Полученные таким образом символы последовательным кодом через первый выход блока 2 проверки четности А-разрядной комбинации поступают на вход счетчика-распределителя 3 и одновременно через второй выход блока 2 проверки четности А-разрядной комбинации и второй вход счетчика-распределителя 5 на (к+1) тактов в прямой канал связи.

Счетчик-распределитель 3 предназначен для распределения значений (к+1) разрядной комбинации по (к+1) сумматорам. При завершении передачи к-й комбинаций сумматоры определяют четность информационных и проверочных символов на одноименных позициях в этих комбинациях. Состояние сумматоров после обработки к комбинаций соответствует проверкам на четность по вертикали в традиционной системе кодов произведений. Для получения подобных проверок счетчик-распределитель 3 связан с регистром 4 вертикальных проверок ровно (к+1) выходами.

Регистр 4 вертикальных проверок предназначен для фиксации через к*(к+1) тактов работы кодера проверок четности по вертикали. При обработке к комбинаций в регистре вертикальных проверок фиксируется последовательность проверок четности по вертикали для первых к переданных комбинаций.

При этом формирование проверок четности по вертикали на основе первых кх(к+1) бит можно представить массивом данных вида:

' 110 0 Л 0 110 10 0 1 ч0 0 1 1,

Указанный массив в регистре 4 вертикальных проверок не формируется. В этом блоке образуется только нижняя строка матрицы: 0011. Для передачи этой строки в канал связи через второй выход регистра 4 вертикальных проверок необходимо задержать входящий поток информационных бит ровно на (к+1) такт. С этой целью через каждые к*(к+1) тактов работы кодера из регистра 4 вертикальных проверок на его первый выход передается сигнала управления на один вход блок 9 управления, который переводит буфер 1 входящей информации во второй режим работы. За время блокировки буфера 1 входящей информации,

регистр 4 вертикальных проверок через второй выход и первый вход счетчика-распределителя 5 на (к+1) тактов передает проверочные символы по вертикали (в нашем примере 0011) в прямой канал связи.

Таким образом, поочередно через второй и первый входы счетчика-распределителя 5 на (к+1) тактов и его главный выход в прямой канал связи транслируется последовательность:

...1100010110010000 1111111100110011 0011100101101100.

Разрывы между группами символов показаны только для удобства восприятия текста и в реальной системе они отсутствуют. Эту последовательность образно можно представить в виде трех массивов (матриц), каждый из которых назовем слоем гиперкода размерности 3D:

'0 0 0 0У 0 0 1 1У110 0 ^ 100100110110 .010111111001. ч 110 0){1 1 1 0 0 11,

Продвигаясь по счетчику-распределителю 5 на (к+1) тактов, передаваемая последовательность подвергается анализу, в ходе которого символы из каждого слоя с номерами Ху оцениваются сумматором 6 проверок 3D. Также в счетчике на (к+1) тактов символы новой последовательности распределяются по (к+1) сумматорам. При передаче к слоев сумматоры определяют четность информационных и проверочных символов на одноименных позициях в этих комбинациях. Состояние сумматоров после обработки к слоев соответствует проверкам на четность 3D в системе гиперкода. Для получения подобных

проверок счетчик-распределитель 5 на (к+1) тактов связан с сумматором 6

2

проверок 3D (к+1) выходами.

2

Сумматор 6 проверок 3D предназначен для фиксации через к*(к+1) тактов проверок четности 3D. Сумматор 6 проверок 3D имеет (к+1) выходов, занумерованных от 1 до (к+1) и подключенных к входам накопителя 7 проверок 3D. Проверка четности 3D представляет собой (к+1) слой гиперкода, который можно представить в виде матрицы:

0000 110 1 10 0 1 1111

Этот слой не передается в канал связи без специальной команды.

Накопитель 7 проверок 3D предназначен для сохранения символов проверки 3D и передачи их последовательным кодом в прямой канал связи только при поступлении запроса. Данный блок имеет (к+1) входов и 1 управляющий вход. Управляющий вход подключен к первому выходу блока 8 выделения запроса. Выход накопителя 7 проверок 3D объединен с главным выходом счетчика-распределителя 5 на (к+1) тактов и подключен к прямому каналу связи. При поступлении сигнала запроса из блока 8 выделения запроса в накопитель 7 проверок 3D через второй выход блока выделения запроса 8 и другой вход блока 9 управления подается команда в буфер 1 входящей информации о переводе кодера в режим три.

Таким образом, основная скорость представленного в примере кода R=0,56. При необходимости передачи добавленной по запросу избыточности скорость кода принимает значение R=0,42. Представленная конструкция кодера способствует поддержанию синхронизации кодера и декодера системы обмена данными, поскольку добавляемая избыточность в точности соответствует одному слою данных и требует специальных указателей для выделения добавленной избыточности.