автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Метод, алгоритмы и устройство коррекции ошибок архивной оптической памяти

На правах рукописи /

ГРАФОВ ОЛЕГ БОРИСОВИЧ

МЕТОД, АЛГОРИТМЫ И УСТРОЙСТВО КОРРЕКЦИИ ОШИБОК АРХИВНОЙ ОПТИЧЕСКОЙ ПАМЯТИ

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

005557895

1 5 2015

КУРСК-2014

005557895

Работа выполнена в Юго-Западном государственном университете

Научный руководитель: доктор технических наук, доцент

, Егоров Сергей Иванович

Официальные оппоненты: Овечкин Геннадий Владимирович

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

Крыжевич Леонид Святославович

кандидат технических наук, Курский государственный университет, кафедра математического анализа и прикладной математики, доцент

Ведущая организация: Пензенский государственный универ-

ситет (г. Пенза)

Защита диссертации состоится «2,8»ф£ЬРАЛЯ 2015 г. в/УЖасов на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: г. Курск, ул. 50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке Юго-Западного государственного университета и на сайте Юго-Западного государственного университета, http://swsu.ru

Автореферат разослан «2БРЯ 2014 г.

Ученый секретарь диссертационного совета

Титенко Евгений Анатольевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Одним из основных методом защиты данных от ошибок, вызываемых дефектами поверхности оптического диска, является коррекция ошибок с помощью помехоустойчивых кодов Рида-Соломона. Использование этих кодов для обеспечения надежного хранения данных в оптической дисковой памяти исследовалось в работах N.Glover, Б.А. Савельева, А.П. Типикина, С.И. Егорова и др.

На практике для коррекции ошибок кодами Рида-Соломона применяют алгоритмы синдромного декодирования, допускающие простую аппаратную реализацию (алгоритм Питерсона-Горенстейна-Цирлера, алгоритм Берлекэмпа-Месси, алгоритм Евклида). Однако в связи с тем, что указанные алгоритмы не используют дополнительную «мягкую» информацию, получаемую из канала, потенциальные корректирующие способности кодов Рида-Соломона реализуются не полностью. Значительно большую эффективность коррекции ошибок могут обеспечить алгоритмы декодирования с мягкими решениями.

R. Ketter и A. Vardy предложили алгебраический алгоритм мягкого декодирования кодов Рида-Соломона, который базируется на списочном алгоритме жесткого декодирования, предложенном V. Guruswami и М. Sudan. Алгоритм Ketter-Vardy устанавливает различные значения кратности для каждой интерполяционной точки на основе информации о мягких решениях. Сложность этого алгоритма растет полиномиально относительно длины кодового слова (не так быстро как у алгоритма Чейза), однако она остается слишком высокой для кодов Рида-Соломона, используемых в оптической памяти.

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

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

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

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

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

2. Создание метода и алгоритмов мягкого декодирования кодов Рида-Соломона с приемлемой вычислительной сложностью.

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

4. Разработка программной модели и исследование эффективности исправления ошибок разработанным устройством с помощью имитационного моделирования на ЭВМ.

Объект исследований - средства исправления ошибок, возникающих в каналах записи/воспроизведения накопителей архивной оптической памяти.

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

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

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

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

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

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

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

Практическая ценность работы состоит в следующем:

- Созданные алгоритмы мягкого декодирования кодов Рида-Соломона позволяют значительно повысить эффективность применения этих кодов в архивной оптической памяти. Уровень ошибочных кодовых слов в считанных данных уменьшается на 1 - 2 порядка.

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

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

Реализация и внедрение.

Диссертационная работа выполнена при поддержке гранта ФЦП «Научные и научно-педагогические кадры инновационной России» №14.В37.21.0621 по НИР 1.124.12 «Высокоэффективные методы, алгоритмы и аппаратные средства коррекции ошибок в беспроводных каналах доступа к широкополосным мультимедийным услугам» и НИР 1.204.12 «Исследование и разработка высокоэффективных методов и алгоритмов декодирования кодов Рида-Соломона».

Основные научные результаты и выводы диссертационной работы внедрены в научно-исследовательском центре (г. Курск) ФГУП «18 ЦНИИ» МО РФ, ООО «Техно-

логии комфорта и Безопасности Черноземья», а также используются на кафедре вычислительной техники ЮЗГУ при преподавании дисциплин «Технические средства защиты и сжатия информации» и «Сети и телекоммуникации».

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

Соответствие диссертации паспорту научной специальности. Согласно паспорту специальности 05.13.05 - Элементы и устройства вычислительной техники и систем управления, проблематика, рассмотренная в диссертации, соответствует пунктам 1, 2 и 3 паспорта специальности (1. Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления. 2. Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик. 3. Разработка принципиально новых методов анализа и синтеза элементов и устройств вычислительной техники и систем управления с целью улучшения их технических характеристик.).

Апробация работы. Основные положения диссертационной работы докладывались и были одобрены на Международных и Российских научно-технических конференция: МНТК «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем» (г. Воронеж, 2009 г.), МНТК «Распознавание -2010» (г. Курск, 2010 г.), МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2010 г.), МНТК «Медико-экологические информационные технологии» (г. Курск, 2011 г.), МНТК «Цифровая обработка сигналов и ее применение - 08РА-2011» (г. Москва, 2011 г.), МНТК «Распознавание -2012» (г. Курск, 2012 г.), МНТК «Цифровая обработка сигналов и ее применение - 08РА-2012» (г. Москва, 2012 г.), РНТК «Информационные системы и технологии» (г. Курск, 2012 г.), МНТК «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем» (г. Воронеж, 2013 г.), а также на научных семинарах кафедры вычислительной техники ЮЗГУ с 2009 по 2014 г.

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

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации лично соискателем предложено: в [2,11,14] метод мягкого декодирования кодов Рида-Соломона, в [3,4,11,16] алгоритмы мягкого декодирования кодов Рида-Соломона, в [4,6,8,9] структурно-функциональная организация устройства декодирования кодов Рида-Соломона, в [1,5,7] методика исследования корректирующих возможностей кодов Рида-Соломона, в [12] анализ зависимости эффективности коррекции ошибок от отношения сигнал/шум.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 155 страниц текста (с учетом приложений) и иллюстрируется 40 рисунками и 13 таблицами; список литературы включает 71 наименование.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Коды Рида-Соломона определяются над конечным полем О?(¿¡=2™) и характеризуются параметрами (п,к,<1), где п - длина кодового слова, к - количество символов полезной информации в кодовом слове и с/ - минимальное кодовое расстояние. Число гарантированно исправляемых ошибок РС-кодом tc

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

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

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

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

Списочное декодирование обеспечивает исправление / = /с+ т (х - число дополнительно исправляемых ошибок) ошибок путем аналитического продолжения алгоритма Берлекэмпа-Месси, вычисляющего полином локаторов ошибок Л<2'с)(х) и вспомогательный полином Ва'с\х), еще на 2т итерации.

Аналитическое продолжение алгоритма на две итерации описывается формулой

ниже:

П)

где Д2,с+1,-Д2(с,2 - неизвестные невязки, 5* = 1, если Д*Ф 0 и 21*./ <к-1, иначе 8* = О, Ц,

- формальная степень полинома локаторов ошибок 1^к)(х).

Аналитическое продолжение на 2г итерации может быть получено применением формулы (1) г раз:

W, (2)

где 5 = {5*, A=2/c+ 1,..., 2^2т}, Д = {Д*, k=2tc+ I,..., 2<с+-2т}.

Наборам неизвестных невязок соответствуют различные полиномы Л(2'с+2г,(*). Известно, что полином локаторов ошибок А (х) обращается в нуль, когда* принимает значения обратные к локаторам ошибочных символов. Представляют интерес полиномы Л<2'с+2г>(*) со степенью tc + г, которые имеют точно tc+T корней в GF(g). Множество допустимых корней полинома Л(2'с+2г>(х) составляет { а",а \а 2,..., а4""2',«"4 )} (а - примитивный элемент поля GF(g)). После подстановки элементов этого множества в уравнение (2), получается следующее:

/ = 0,1,...,и-1 (3)

где (а ') и В(2'с)(а ') - коэффициенты дискретного преобразования Фурье полиномов

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

невязки A2jc+i>'A2/c+2>—.Дг/с+гг-

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

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

В процессе поиска осуществляется перебор (2г-1) позиций ошибок наименее надежных символов в области ETS (Error Trapping Scope). Для каждого набора из (2г-1) позиций вычисляется последовательность ],ц/2].....¿[i2r_, i возможных значений не-

• £[f, шм.....£['->,] .

вязки А и осуществляется поиск значении Д, которые встречаются в по-

следовательности точно (fc+1-г):

= ЛЧ'11Ц,21.....i[,2rl = .....RLV2t ])

hr = hr-l+hn-l), (4)

где:

F'iLWiW2],..., Цг2Лкщ1>кт21.....=

V(JlJj.....

j\<h<<h

1.2.....2 г}

П(а +«""1) П^'+^'ЯТЛ.. 1

v(*1.a2) v{*u2j *=1 ■:. 'к

*1<*2 и<*2

k\,kleJ HJt 26(1.2....;)U . '

{а(-2,ч)'А(2'с)(«")/Д(2'е)(а"')в противном случае -я = =Г-|s+l|, о2 = г-|s|.

Если такие значения Д найдены, то позиции ошибочных символов даются значениями индексов Цг^Ц}^,...,!^^^ последовательности и множеством значений индекса Ц}2т], указывающего на эти Д. Значения ошибочных символов могут быть найдены с использованием формулы Форни.

Формализация метода в виде процедуры мягкого декодирования кодов Рида-Соломона приведена ниже и предусматривает выполнение следующих этапов:

1) Вычисляются коэффициенты многочлена синдромов S(x). Если они нулевые (это соответствует случаю отсутствия ошибок), выполняется переход к п. 14.

2) Определяются многочлен локаторов ошибок Л(2'с)(х), вспомогательный многочлен

и формальная степень многочлена локаторов Lllc после выполнения 2tc итераций алгоритма Берлекэмпа-Месси.

3)Если L2tc < tCj находятся корни многочлена Л<2'с)(дг). В случае равенства числа корней значению Ь2,с в качестве локаторов ошибочных символов принимаются обратные к корням величины. Значения ошибок определяются по формуле Форни. В список добавляется только верная конфигурация ошибок, ложная - отфильтровывается.

4) Определяется управляющая переменная s = tc-L2 . Если s>r или л<-г, выполняется переход к п. 13.

5) Выполняются преобразования Фурье многочленов Л(2'с)(.х) и Ва'с\х).

6) Если i >0, находятся значения дробей Л, = «(2l+1)' Я <2'с' (« ) / Л(2'с > (а ), или Äf =а(-2*-,>'Л<2'с)(а"')/5(г'е>(а"') в противном случае (/=0,...и-1).

7) Устанавливается начальное значение счетчика дополнительно исправляемых ошибок v=l.

8) Вычисляются вспомогательные переменные: / = 2v, ol = v - |s+l|, о2 = v - |s|, w = ic+l-v.

9) Устанавливается начальное значение счетчика систем уравнений: sc = 1.

10) Формируются последовательности £/.[/, u[,2],...,д/,,,] (4) возможных значений ЛЩШ12].....Щ]

невязки ¿i для наиболее вероятных наборов индексов )'ь /2,...,/м и осу-

ществляется поиск значений Д, которые встречаются точно w раз в какой-то из этих последовательностей.

Если такие значения Д найдены, то позиции ошибочных символов даются значениями индексов Д/,],Д»2],...,^[/2г_,] последовательности и множеством значений индекса Ц}2,], указывающего на эти Д. Значения ошибочных символов находятся с использованием формулы Форни. Верные конфигурации ошибочных символов добавляются в список, ложные отфильтровываются.

В случае добавления конфигураций ошибок в список и выполнении условий выхода exit = 1 или exit = 2 перебор индексов i'i, /2, ... /'м прекращается. Если exit= 1, осуществляется переход к п. 13, если exit - 2 - переход к п. 11.

11) Если v=-s, осуществляется переход к п. 12, в противном случае: sc=sc+1,1=1-l,ol=ol-l,o2 = o2-l,w = w+l.

Если se < (v-|í I), осуществляется переход к п. 10.

12) v=v+l. Если v< т, то осуществляется переход к п.8.

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

14) Конец.

В описании процедуры мягкого декодирования использованы следующие переменные: L - таблица, содержащая номера позиций символов, упорядоченных по надежности; se - счетчик систем уравнений; exit -режим завершения работы процедуры декодирования (0 - без досрочного выхода из процедуры декодирования, 1 - досрочный выход после 1-го найденного вектора ошибок; 2 - после найденных векторов ошибок для каждой системы уравнений).

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

На основе предложенного метода разработано семейство алгоритмов мягкого декодирования кодов Рида-Соломона, отличающихся реализацией перебора индексов /',, /2>.. .,i'm и различными условиями выхода из циклов этапа 10.

Наиболее очевидный алгоритм перебора индексов iь i2,...,ii-u допускающий простую аппаратную реализацию, приведен ниже в виде псевдокода.

for i = / - 2 downto 0 do

/_mass/v('] = LmassM'l + 1

If i_massiv[il * CycleLimits[CycleLimitsPointer + /] then

fory = 1to/-/-2do

i_massiv[i+jl = i_massH{i] + i

end for

goto MainCycle II Переход к вычислению j

end If

end for

Массив i_massiv[[\ содержит набор индексов ;ь h,—Л он инициализируется следующим образом:

for i = 0 to М do /_mass/vM = /.

Диапазон перебора индексов i¡, /2,...,г'ы ограничен первыми наименее надежными «г позициями символов из таблицы L. Для этого используется массив CycleLimits.

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

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

Более эффективный алгоритм мягкого декодирования может быть получен на основе следующего алгоритма перебора индексов i¡, i2,...,ii-\-

if IndSerLen > 1 then

IndSerLen = IndSerLen -1

forí= Oto IndSerLen -1 do . -

/_massM'] - i

end for

i_massiv[lndSerLen] = IndSerPos +1 IndSerPos = IndSerLen - 1

else

IndSerPos = IndSerPos + 1 / massM°] = IndSerPos / = 1 '

while IndSerPos + 1 = i_massiv[i\ do 1 = 1+1

IndSerLen = IndSerLen + 1 IndSerPos = IndSerPos + 1 if ; = /- 1 then break end If end while

end if

if i_massiv[l- 2] < CycleUmits[CycleLimitsPointer +1-2] then goto MainCycle

end if

Значения управляющих переменных задаются следующим образом:

IndSerLen = 1-1 IndSerPos = IndSerLen -1.

В диссертации этот алгоритм обозначается с помощью аббревиатуры AS, где А -от англ., algorithm - алгоритм, S - от англ., serial - серийный.

Для указания режима завершения работы процедуры декодирования к аббревиатуре алгоритма добавляется буква Е (exit) с последующей цифрой, обозначающей режим завершения. Например, версия алгоритма декодирования, использующая 1-й режим завершения работы процедуры декодирования, будет обозначаться как AS El.

Путем имитационного моделирования на ЭВМ исследовалась эффективность исправления ошибок разработанными алгоритмами мягкого декодирования для ряда популярных PC-кодов, определенных над полем GF(28) с минимальным кодовым расстоянием </=17. При моделировании использовалась модель канала с Гауссовским шумом (AWGN) и модуляцией BPSK. (binaiy phase shift keying). В качестве меры надежности символа принималось минимальное значение модуля LLR составляющих символ бит.

На рис. 1 приведены результаты исследования эффективности алгоритма ASE1 в виде графика зависимостей FER (Frame Error Ratio) от Eb/N0 (отношения энергии сигнала на информационный бит к односторонней спектральной плотности шума).

Цифрами обозначены: 1 - классический алгоритм декодирования, исправляющий tc = 8 ошибок без использования мягких решений; 2 - алгоритм ASE1 с радиусом декодирования tc+1; 3 - алгоритм ASE1 алгоритм с радиусом декодирования tc+2: 4 - алгоритм Ketter-Vardy.

Результаты исследования показывают целесообразность исправления алгоритмом ASE1 до двух дополнительных ошибок. При этом дополнительный кодовый выигрыш составит около 0,3dB. Кривая 3, соответствующая коррекции двух дополнительных ошибок, практически совпадает с кривой 4, отображающей результаты работы Де-

Eb- No <лШ >

Рис. 1. Зависимость FER от Eb/No для

кодера Ketter-Vardy с мультиплиеити 2. Проведенные исследования зависимостей FER от Eb/No для различных кодов Рида-Соломона показали, что, начиная с некоторого значения, увеличение г не приводит к значимому уменьшению FER. При этом наблюдается увеличение числа случаев ложной коррекции кодовых слов.

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

еь/NoidB) Эффект от использования фильтра-

ции показан на графике на рис. 2, на котором приведены кривые зависимостей FER от Eb/No для алгоритма декодирования с мягкими решениями с использованием фильтрации ASE1F (кривая 1) и алгоритма без использования фильтрации ASE1 (кривая 2) для кода Рида-Соломона (255,239).

Рис. 2 показывает, что использование фильтрации по совокупной надежности позиций ошибок дает дополнительный кодовый выигрыш в 0,14 db. Совпадение точек при значение Eb/No = 5.5 объясняется чрезмерно высоким значением шума в канале, при котором алгоритм с использованием фильтров не дает преимущества.

Эффективность коррекции ошибок разработанным алгоритмом мягкого декодирования с использованием фильтрации ASE1F в сравнении с эффективностью наиболее известного алгоритма мягкого декодирования Ketter-Vardy для РС-кода (255,239) показана на рис. 3.

На рис. 3 цифрами обозначены: 1 — предложенный алгоритм ASE1F, 2 -классический алгоритм декодирования с жесткими решениями, исправляющий 8 ошибок, 3 - алгоритм Ketter-Vardy с мультиплиеити ю=2, 4 - алгоритм Ketter-Vardy m=4, 5 - алгоритм Ketter-Vardy -г ..з ... -s m=8,6-алгоритм Ketter-Vardy m=100.

Рис. 3. Зависимость FER от Eb/No для РС-кода (255,239) над GF(28) График на рис. 3 показывает, что предложенный алгоритм мягкого декодирования уступает по эффективности коррекции ошибок лишь алгоритмам Ketter-Vardy с мультиплиеити т=8 и т=100, которые нецелесообразно использовать на практике из-за большой вычислительной сложности.

Рис. 2. Зависимость FER от Eb/No для РС-кода (255,239) над GF(28) для t = 11 с фильтрацией и без нее

В диссертации получены оценки вычислительной сложности предложенных алгоритмов мягкого декодирования путем имитационного моделирования на ЭВМ. Оценка сложности алгоритма А8Е1Г при декодировании кода Рида-Соломона (255, 239) представлена на рис. 4, на котором приведен график зависимости £ (вычислительной сложности в среднем) от ЕЬ/Ыо.

_____щыядц_____Из графика на рис. 4 сделаны следующие выводы. Вычислительная сложность алгоритма ЛЗЕ1Р при исправлении одной дополнительной ошибки (1=9, т=1) возрастает приблизительно в 1.5 раза относительно вычислительной сложности классического алгоритма декодирования (/=8). При исправлении двух дополнительных ошибок (¿=10, 1=2) вычислительная сложность алгоритма А8Е1Е увеличивается примерно в 4 раза (для ЕЫИо=6,5). При исправлении трех дополнительных ошибок (<=11, 1=3) вычислительная сложность алгоритма Рис. 4. Зависимость вычислительной слож- А8Е1Р возрастает примерно на 2 поряд-ности алгоритма £ от ЕЬ/Ыо для разного ко- ка по сравнению со стандартным деко-

личества исправляемых ошибок / дированием (<=8).

Таким образом, разработанный алгоритм мягкого декодирования А5Е1Р обладает приемлемой вычислительной сложностью при исправлении двух дополнительных ошибок.

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

Структурная схема устройства коррекции ошибок приведена на рис. 5. . На вход устройства подаются /и-разрядные символы кодового слова{г,}, принятого из канала, сопровождаемые значениями их надежности {геи}. При этом устройство ; выполняет алгоритм мягкого декодирования АБЕШ. На выход устройства выдаются символы {с,} кодового слова с исправленными ошибками.

Устройство содержит блок памяти данных 100, предназначенный для временного хранения символов исправляемых кодовых слов; блок вычисления синдромов 200; процессор, реализующий операции в полях Галуа, 300; блок дискретного преобразования Фурье 400; блок, осуществляющий поиск позиций ошибок веса больше <с, 500; блок сортировки позиций символов 600, осуществляющий сортировку позиций кодового слова в соответствии с их надежностью; блок вычисления значений ошибок 700; сумматор элементов поля Галуа 800.

Процессор 300 выполняет алгоритм Берлекэмпа-Месси, вычисляя в соответствии с ним полиномы за 2/с итераций (2-ой этап процедуры декодиро-

вания).

Рис. 5. Структурная схема устройства коррекции ошибок архивной оптической

памяти

Кроме того, на основе информации о расположении ошибок в кодовом слове {РЕ}, полученной от блока поиска позиций ошибок 500, процессор Галуа вычисляет итоговый полином локаторов:

ЛМ = П(1-логР£'). (5)

м

Также процессор 300 вычисляет полином значений ошибок О(х) = Л(дг) • 5(х) тос! х'1~' и формальную производную Л'(*) полинома локаторов ошибок Л(х), необходимые для работы блока 700.

Блок ДПФ 400 выполняет преобразование Фурье полиномов А°'с\х) и В'-2'с'(х) (5-й этап процедуры мягкого декодирования). Также он вычисляет коэффициенты А, =а' и дроби Л,- (6-ой этап процедуры мягкого декодирования).

Блок 700, используя полиномы и Л'(лг), вычисляет значения ошибок в

найденных позициях ошибок {РЕ}. Блок реализует вычисления по формуле Форни. Из ошибочных символов кодового слова, считываемых из буфера данных 100, с помощью сумматора 800 вычитаются полученные значения ошибок (13-й этап процедуры мягкого декодирования).

Самым важным и самым ресурсоемким блоком устройства коррекции ошибок является блок поиска позиций ошибок 500. БППО реализует поиск конфигураций ошибок веса Гс+1 и /с+2 с использованием информации о надежности символов кодового слова БППО выполняет 7-12 этапы процедуры декодирования, вычисляя последовательности невязок и подсчитывая количества одинаковых значений невязок в этих последовательностях.

Блок 500 состоит из 2-х блоков вычисления невязки А (БВН); 2-х блоков подсчета невязок Д ' (БПН); коммутатора; регистра-защелки; блока памяти коэффициентов.

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

В случае исправления до 2-х дополнительных ошибок (v < 2) формула для вычисления невязок (4) может быть записана в виде следующих выражений (6-14). Вид выражения зависит от значений следующих переменных, используемых в алгоритме декодирования: v (счетчик числа дополнительно исправляемых ошибок), s (управляющая переменная shift s = tc - Lbc ) и se (счетчик систем уравнений). Для упрощения записи ниже используются следующие обозначения:

Выражения для вычисления неизвестной невязки (4) при исправлении двух дополнительных ошибок v = 2 имеют следующий вид.

Для случая s=0, îc=1 :

Л (AJ+ Ак )(Aj + At )(Л- + 4 Ж + (4 + 4 Х4 + 4 )(Л + A, )R, + (4 + Aj Х4+4 ЭД + (4 + 4 Х4 + 4 + (4 + 4 Х4+A )R,R, +

+{А, + 4X4 + 4X4 + A,)Rk + (А, + 4X4 + АХ4 + A,)R, + (А, + 4X4 + A,)RjRt + (А, + 4X4 + 4)«Д+(Д + 4X4 +

А,В11-(а-') ГДеЛ'= Л2'с(а~')

Совместимое подмножество из fc + 2 уравнений может содержать одно уравнение, для которого Л2'с (от"') = 0 . Тогда:

д=_(4+4X4+4X4+4)_

(Al+A,)(Aj+At)Rl +(4+4X4 +4+(4+4X4 +4 Ж '

Для случая 5=-1, ïc= 1 :

(4 +4X4 + M +4X4 +4Жду+(4+4Х4 +4ЖЛ + (4 + А )(4 + 4 Х4 + 4 Ж + (4+4 Х4+4 Х4 + 4 Ж + +(Aj + 4 )(Aj + 4 ЗД + (Aj + А, )(4 + Ак )RjR, + (Л + А, )(4 + Л,

+(^+4)(4+4Х4+4)^+(4+4Х4+4Х4+А)Л/

А1Л2'с(а~') где ^ - ■

Совместимое подмножество из /с + 2 уравнений может содержать одно уравнение, для которого

В с (а'') = 0. Тогда:

(4 +4X4 +4Ж +(4 +4X4 +4Ж +(4 +4X4 +4Ж,

(4 + 4X4 + 4 )(4 + 4 ) ' ()

Для случая s=l, îc=1

(4+ЛД4+ЛХ4+4) С4+4X4 +4X4 +4Ж +(4 +ЛХ4+4X4 + 4)*, +

(8)

д=-

(А/+ака/+А)(А+А)__(10)

+ ÎAl+A1){Al+Al)(Aj + A,)Rl+(At+A1)(A1 + AtXA]+Ak)Rl '

где Л2'с(а~') *

Для случая s=-2, sc=l :

(Л,+4 Х4 M Х4 M Ж + (4+4 )(4 + 4 + 4 )Ду ,

(Al+AJ)(Af+Ak){Al+A,)(Aj + At ){Aj + А, ){Ак + А, )

(А, + А,)(4 + 4)(Лу + A,)Rk НА+АХА + A)(aJ + A)Ri .

В2'с (а' Для случая s=0, jc=2:

(Aj + Ak)Rt +(А+АЩ+(А+АЖ,

OD

где R,--Г17

гдеЛ'= •

Выражения для вычисления неизвестной невязки (4) при исправлении одной дополнительной ошибки V = 1 имеют следующий вид.

Для случая s=0, sc= 1 :

Д = <13>

R, + Rj

Для случая s=-l, sc=l:

д = (14)

Л + Л

Проведенный синтез БВН учитывает совпадения выражений для числителей и знаменателей большинства формул 6-14. Совпадают: 1) числитель формулы (6) и знаменатель формулы (8) (обозначим соответствующее выражение как Q\), 2) знаменатель формулы (6) и числитель формулы (8) (Q2), 3) знаменатель формулы (10) и числитель формулы (11) (Qj), 4) числитель формулы (10) и знаменатель формулы (11) (04), 5) знаменатель формулы (7) и числитель формулы (9) (g5), 6) числитель формулы (7), знаменатель формулы (9) и знаменатель формулы (12) (ß6), 7) числитель формулы (13) и знаменатель формулы (14) (ß7), 8) числитель формулы (14) и знаменатель формулы (13)

Функциональная схема синтезированного блока БВН 510 изображена на рис. 6. БВН включает: блок произведений дробей Я, 511, блок произведений коэффициентов At 512, коммутаторы 513.1, 513.2 и 5133, умножители элементов поля Галуа 514.1-514.11,сумматоры элементов поля Галуа 515.1, 515.2 и 515.3, инвертор элементов поля Галуа 516, селектор нулевого элемента поля Галуа 517.1, схему сравнения кодов 517.2, логические элементы ИЛИ-НЕ 518 и И 519.

Блок вычисления невязок реализует вычисления невязок в соответствии с приведенными выше формулами (6-14) для исправления одной (<с+1) или двух (fc+2) дополнительных ошибок.

i_L

ИИ«. 11 i 2 3 4 5 6 7 8 9 10

it

4

БПК Л. 6

1 2 >4)011 8'

На функциональной схеме рис. 6 значения Qh бз формируются на выходах сумматора 515.3, Q2, Qs - на выходах сумматора 515.1, f?4 - на выходах 8 БПК Ai 512, Qs - на выходах 7 БПК А, 512, б? - на выходах 9 БПК А, 512, 0„ - на выходах сумматора 515.2.

Реализация вычисления совпадающих частей Q1 — Qs различных выражений (6-14) на одном и том же оборудовании позволяет уменьшить сложность реализации самого сложного блока устройства коррекции ошибок блока БВН примерно в два раза.

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

Рис. 6. Функциональная схема блока вычисления невязок

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

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

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

На рис. 7 приведены р^зудьтаты имитационного моделирования разработанного устройства коррекции ошибок в виде графика зависимости FER (Frame Error Ratio) от

Eb/No для PC-кода (120, 104), используемого в архивных оптических накопителях информации, при исправлении /=10 ошибок.

На графике рис. 7 показаны кривые:

- Без квантования - без применения квантования информации о надежности символов кодового слова;

- 1 бит - квантование информации одним битом;

- 2 бита — квантование информации двумя битами;

- 3 бита - квантование информации тремя битами.

Рис. 7. Зависимость FER от Eb/No для /=10 при разной степени квантования

Из графика на рис. 7 сделан вывод, что для РС-кода (120, 104) при исправлении /=10 (т=2) ошибок целесообразно использовать квантование 3 битами, поскольку кривые эффективности с применением степени квантования 3 бита практически совпадают с кривыми эффективности исправления ошибок без использования квантования.

На рис. 8 приведены результаты исследования эффективности коррекции ошибок разработанным устройством в виде графика зависимостей FER (Frame Error Ratio) от Ef/N0 для PC-кода (120, 104), используемого в архивных оптических накопителях информации.

Eh.NV(JB>

Цифрами обозначены: 1 - классический декодер, исправляющий /с = 8 ошибок без использования мягких решений; 2 - разработанный декодер, реализующий алгоритм ASE1F с радиусом декодирования tc+1; 3 - тот же декодер с радиусом декодирования /с+2.

Рис. 8 показывает, что разработанное устройство коррекции ошибок обеспечивает снижении уровня ошибочных кадров (FER) в оптической памяти в 12.6 раза.

Рис. 8. Зависимость FER от Eb/No для РС-кода (120,104)

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

Eb/No (dB)

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

3. На основе предложенного метода разработано семейство алгоритмов мягкого декодирования кодов Рида-Соломона. Приведены результаты исследования их эффективности. Разработанные алгоритмы декодирования позволяют значительно повысить эффективность применения высокоскоростных кодов Рида-Соломона в системах хранения и передачи информации за счет исправления дополнительных ошибок. Например, алгоритм ASE1F обеспечивает дополнительный кодовый выигрыш по сравнению со стандартным декодированием около 0,42 dB. Эффективность алгоритма ASE1F выше, чем эффективность алгоритма Ketter-Vardy с мультиплисити 2.

4. Проведены исследования вычислительной сложности разработанного алгоритма мягкого декодирования кодов Рида-Соломона ASE1F. Вычислительная сложность алгоритма при исправлении одной дополнительной ошибки (í=9, т=1) возрастает приблизительно в 1.5 раза относительно вычислительной сложности стандартного декодирования (/=8). При исправлении двух дополнительных ошибок (/=10, п=2) вычислительная сложность алгоритма ASE1F увеличивается примерно в 4 раза (для Eb/No=6,5).

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

6. В результате имитационного моделирования на ЭВМ устройства коррекции ошибок показано, что устройство обеспечивает снижение уровня ошибочных кадров (FER) в архивной оптической памяти в 12,6 раза.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В рецензируемых научных журналах и изданиях, рекомендуемых ВАК:

1. Егоров, С.И. О возможности исправления дополнительных ошибок в кодах Рида-Соломона [Текст] / С. И. Егоров, О. Б. Графов // Телекоммуникации. - 2011. - №4 -С. 15-18.

2. Графов, О.Б. Мягкое декодирование кодов Рида-Соломона [Текст] / О.Б. Графов, С.И. Егоров, B.C. Титов // Известия Юго-западного государственного университета. Серия. Управление, вычислительная техника, информатика. Медицинское приборостроение. - 2012. - №2.-4. 1. - С. 17-23.

3. Егоров, С.И. Построение алгоритмов мягкого декодирования кодов Рида-Соломона на основе алгоритма списочного декодирования [Текст] / С.И. Егоров, О.Б. Графов, Ж.Т. Жусубалиев, Э.И. Ватутин // Известия Юго-западного государственного университета. Серия. Управление, вычислительная техника, информатика. Медицинское приборостроение. - 2012. - №2.-4. 2. - С. 28-33.

4. Егоров, С.И. Декодер кода Рида-Соломона для цифрового телевидения [Текст] / С.И. Егоров, B.C. Титов, О.Б. Графов // Известия вузов. Приборостроение. - 2013 - №6 - С. 50-53.

5. Egorov, S.I. On the capacities for correcting additional errors in Reed-Solomon codes [Text] / S.I. Egorov, O.B. Grafov // Telecommunications and Radio Engineering (English translation of Elektrosvyaz and Radiotekhnika). - 2013. - V.72 (# 13). - P. 1227-1233 (Индексируется в SCOPUS).

Патент на изобретение:

6. Егоров, С.И. Патент 2441318 Российская Федерация Н03М13/45. Устройство декодирования кодов Рида-Соломона [Текст] / С.И. Егоров, О.Б. Графов заявл 17.08.2010, опубл. 27.01.2012, Бюл. №3,2012. '

В других изданиях:

7. Егоров, С.И. О корректирующих возможностях декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния [Текст] / С.И. Егоров, О.Б. Графов, Д.Г. Барышок // Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем: сб. трудов. -Воронеж: «Научная книга», 2009. - Вып. 14. - С. 306-308.

8. Егоров, С.И. Декодер кодов Рида-Соломона, исправляющий ошибки за границей половины минимального кодового расстояния с использованием мягких решений [Текст] / С.И. Егоров, О.Б. Графов // Распознавание - 2010: сб. материалов IX МНТК. - Курск: ЮЗГУ, 2010. - С. 156-158.

9. Егоров, С.И. Декодер кодов Рида-Соломона, управляемый мягкими решениями [Текст] / С.И. Егоров, О.Б. Графов // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: сб. материалов 16-й междунар науч.-техн. конф. - Рязань, 2010. - С. 55-57

10. Графов, О.Б. Исследование эффективности алгоритма декодирования кодов Рида-Соломона за границей половины минимального кодового расстояния для оптической записи [Текст] / О.Б. Графов // Медико-экологические информационные технологии: сб. материалов XIV Междунар. науч.-техн. конф. - Курск, 2011. - С. 27711. Егоров, С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий

вплоть до п-к ошибок в кодовом слове с использованием мягких решений [Текст] / С.И. Егоров, О.Б. Графов, Д.Г. Барышок // Цифровая обработка сигналов и ее применение -

DSPA-2011: сб. докладов XIII Междунар. конф. -М.: РНТОРЭС им. А.С.Попова, 2011. -С.24-27.

12. Г рафов, О.Б. Коррекция ошибок для архивных оптических дисков типа WORM [Текст] / О.Б. Графов, С.И. Егоров // Распознавание - 2012: сб. материалов X МНТК. - Курск: ЮЗГУ, 2012. - С. 142-144.

13. Графов, О.Б. Устройство коррекции ошибок для голографичекой оптической памяти [Текст] / О.Б. Графов // Распознавание - 2012: сб. материалов X МНТК. -Курск: ЮЗГУ. 2012. - С. 144-146.

14. Графов, О.Б. Мягкое декодирование популярных кодов Рида-Соломона [Текст] / О.Б. Графов, С.И. Егоров // Цифровая обработка сигналов и ее применение -DSPA-2012: сб. докладов XIV Межд\пар. конф. - М.: РНТОРЭС им. А.С.Пспова, 2012. -С.46-49.

15. Графов, О.Б. Вычислительная сложность алгоритма мягкого декодирования кодов Рида-Соломона, используемого в оптических дисках типа WORM [Текст] / О.Б. Графов // Информационные системы и технологии - 2012: сб. докладов I Региональной нэучно-гехнической конференции. - Курск: ЮЗГУ, 2012. - С.53-55.

16. Графов, О.Б. Алгоритмы мягкого декодирования кодов Рида-Соломона [Текст] / О.Б. Графин, С.Л. Егоров, М.В. Бобырь, A.A. Макаревич // Информационные технологии моделирования и управления. - Воронеж: «Научная книга». 2012. - №5 (77). - С. 354-363.

17. Графов, О.Б. Повышение эффективности мягкого декодирования кодов Рида-Соломона с использованием фильтрации по совокупной надежности символов кодового слона |Текст] / О.Б. Графов // Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных-систем: сб. трудов. -Воронеж: «Научная книга», 2013. - Вып. 18. - С. 314-317.

18. Графов, О.Б. Мягкое декодирование кодов Рида-Соломона с фильтрацией векторов ошибок [Текст] / О.Б. Графов // Распознавание - 2013: сб. материалов XI МНТК. - Курск: ЮЗГУ. 2013. - С. 245-248.

19. Графов, О.Б. Синтез блока вычисления невязок устройства декодирования кодов Рида-Соломона [Текст] / О.Б. Графов // Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем: сб. тоудов. - Воронеж: «-'Научная книга», 2014. - Вып. 19. - С. 153-156.

Соискатель О.Б. Графов

Подписано в печать_. Формат 60x84 1/16 .

Печ. л. L0. Тираж ¡ос экз. Заказ Юго-Западный государственный университет.

Издательско-полиграфический центр Юго-Западный государственный университет 305040, Курск, ул. 50 лет Октября, 94.