Содержание к диссертации
Введение
1 Анализ методов, алгоритмов и аппаратных средств коррекции ошибок архивной оптической памяти 13
1.1 Характеристики ошибок в каналах записи-воспроизведения оптической памяти 13
1.2 Методы коррекции ошибок, возникающих в каналах записи-воспроизведения оптической памяти 15
1.3 Применение кодов Рида-Соломона для коррекции ошибок в оптической памяти 17
1.3.1 Определение кода Рида-Соломона 18
1.3.2. Структура сектора данных оптического диска WORM 19
1.3.3. Классическое алгебраическое декодирование кодов Рида Соломона 21
1.4 Алгоритмы мягкого декодирования кодов Рида-Соломона 26
1.4.1 Алгоритм GMD 27
1.4.2 Алгоритм Чейза 27
1.4.3 Алгоритм Чейз 2-GMD 28
1.4.4 Алгоритм Кеттера-Варди 29
1.4.5 Алгоритм SED 30
1.5 Аппаратные средства коррекции ошибок 31
1.5.1 Устройство декодирования кодов Рида-Соломона, исправляющее tC+1 ошибок 32
1.5.2 Устройство декодирования кодов Рида-Соломона, реализующее алгоритм Кеттера-Варди 35
1.6 Выводы 39
2 Создание метода и алгоритмов мягкого декодирования кодов рида-соломона, основанных на списочном синдромном декодировании 41
2.1 Мягкое декодирование, основанное на выборе наиболее вероятного вектора ошибок из списка 41
2.2 Метод мягкого декодирования, основанный на введении управления надежностью символов в процедуру списочного декодирования 44
2.3 Алгоритмы мягкого декодирования 50
2.4 Фильтрация векторов ошибок по совокупной надежности ошибочных символов 55
2.5 Вычислительная сложность алгоритмов мягкого декодирования кодов Рида-Соломона 62
2.6 Выводы 71
3 Разработка устройства коррекции ошибок архивной оптической памяти 74
3.1 Структурно-функциональная организация устройства коррекции ошибок архивной оптической памяти 74
3.1.1 Блок поиска позиций ошибок 80
3.1.2 Синтез блока вычисления невязок 83
3.1.3 Блок подсчета невязок 94
3.1.4 Блок дискретного преобразования Фурье 96
3.2 Оценка сложности устройства коррекции ошибок архивной оптической памяти 100
3.3 Выводы 107
4 Исследование устройства коррекции ошибок архивной оптической памяти путем иммитационного моделирования 108
4.1 Организация программной модели 108
4.2 Методика определения основных характеристик алгоритмов и устройств по программной модели 115
4.3 Выбор степени квантования информации о надежности символов кодового слова на входе устройства 120
4.4 Оценка эффективности коррекции ошибок разработанным устройством 123
4.5 Выводы 124
Заключение 126
Список литературы 128
- Применение кодов Рида-Соломона для коррекции ошибок в оптической памяти
- Метод мягкого декодирования, основанный на введении управления надежностью символов в процедуру списочного декодирования
- Оценка сложности устройства коррекции ошибок архивной оптической памяти
- Выбор степени квантования информации о надежности символов кодового слова на входе устройства
Применение кодов Рида-Соломона для коррекции ошибок в оптической памяти
Первые оптические диски были разработаны на рубеже 70-80-х годов совместными усилиями компаний Sony и Phillips. С тех пор неоднократно значительно менялась технология создания дисков с целью увеличения их емкости. Во всех оптических дисках информация записывается с помощью лазерного луча на движущийся носитель.
Пользователям персональных компьютеров известны следующие технологии оптических дисков: - CD (Compact Disk) - диски диаметром 120 мм емкостью 680 Мбайт (CD-ROM, ISO/IEC 10149, ECMA-130 [54]); - DVD (Digital Versatile Disk) - диски диаметром 120 мм с односторонней однослойной записью (DVD-5) емкостью 4,7 Гбайт [24, 29]; - HD DVD (High Density DVD) - диски диаметром 120 мм с однослойной записью емкостью 15 Гбайт [70]; - BD (Blue Ray Disk) - диски диаметром 120 мм с однослойной записью емкостью примерно 25 Гбайт [69]; - HVD (Holographic Versatile Disk) - голографические оптические диски диаметром 120 мм емкостью 100 Гб (HVD-ROM, стандарт ECMA-378 [71]). Наибольшее распространение получили технологии CD и DVD, которые предусматривают использование следующих основных видов оптических дисков: - не перезаписываемые диски с приставкой ROM (CD-ROM Compact Disk Read Only Memory); - однократно записываемые диски с приставкой R (CD-R Compact Disk Recordable); - диски со стиранием и многократной перезаписью с приставкой RAM (DVD-RAM - Digital Versatile Disk Random Access Memory) или RW (CD-RW - Compact Disk ReWritable). Оптические диски используются не только для хранения данных пользователями персональных компьютеров, но и для построения систем архивирования данных большой емкости.
В диссертации основное внимание уделяется архивным оптическим дискам типа WORM. Диски WORM (Write Once Read Many), допускающие однократную запись и многократное чтение, используются в системах архивирования. Стандарты для таких дисков появились в конце 80-х годов XX века [55] и принимались до самого последнего времени [56].
Оптические диски для архивной памяти имеют разный диаметр (130 мм, 300 мм и 356 мм) и используют различные технологии записи [55-67]. Например, картридж с диском диаметром 130 мм (WORM UDO, стандарт ISO/IEC 17345, ECMA-350 [56]) емкостью 30 Гбайт использует сине-фиолетовый лазер. Дефекты поверхности оптического диска являются причиной относительно высокого уровня ошибок в считанной с носителя информации [1, 20-22, 26, 34, 37, 40, 42-45, 48, 50, 53]. Размер дефекта ограничивается стандартами - 0.3 мм [36]. Частота ошибок воспроизведения накопителей может достигать 10 4 на бит. Характерно группирование ошибок в пакеты.
В стандарте [55] определяются условия «начала жизни» и «конца жизни» оптического диска относительно надежности хранимой им информации. «Начало жизни»: - допустимый интервал вероятности ошибки в бите считанных данных (BER) - (1-5)10-5; - вероятность ошибки в бите скорректированных данных не более 10-12. «Конец жизни»: - BER 10 4; - длина пакетов ошибок 100 бит. В [68] конец жизни носителя для записываемых DVD-R, DVD-RW дисков определяется при условии, что максимальное число строк с ошибочными байтами в 8 последовательных блоках ECC превышает 280, а для DVD-RAM дисков - количество ошибочных байт в 32 последовательных блоках ECC превышает 10"3.
Требуемое значение BER для оптических дисков зависит от выполняемых на ЭВМ приложений и находится в диапазоне 10 12 - 10 15 [52].
Методы коррекции ошибок предназначены для повышения достоверности воспроизводимой или принимаемой информации в каналах с ошибками. В качестве меры достоверности информации используют вероятность ошибок в бите, символе, слове и блоке (секторе, кадре). В диссертации для оценки достоверности данных используются параметры BER (англ, Bit Error Ratio - частота ошибочных бит) и FER (англ., Frame Error Ratio - частота ошибочных пакетов).
На основе анализа источников [22, 23, 27, 41, 47, 49] выявлены известные методы коррекции ошибок, используемые в каналах записи/воспроизведения оптических накопителей информации:
В процессе записи для обхода дефектов, вызывающих постоянные ошибки, используют технику контрольное считывание данных со второго оборота носителя или DRAW (прямое чтение после записи) с помощью отраженного или второго луча. Если ошибки в записи неисправимы, всю запись или ее часть перезаписывают на новое место [22].
Дефекты носителя, возникшие после записи данных, создают ошибки, которые могут быть исправлены только с помощью помехоустойчивых кодов или дублирования информации. Дублирование в разы увеличивает избыточность информации и поэтому в оптической памяти применимо только для служебной информации, небольшой по объему.
Коррекция ошибок с использованием помехоустойчивых кодов является основным методом защиты от ошибок информации, хранимой в оптической памяти. Другие методы защиты используются для устранения неисправимых ошибок. Для применения в оптической памяти к помехоустойчивым кодам предъявлются следующие требования: - малая избыточность; - исправление многократных пакетов ошибок; - существование эффективных алгоритмов декодирования. Коды Рида - Соломона (РС-коды) наилучшим образом подходят под эти требования и являются стандартом в системах защиты от ошибок [22].
Применение кодов Рида-Соломона для коррекции ошибок в оптической памяти
Коды Рида-Соломона являются одним из наиболее популярных классов корректирующих кодов, предложенным в 1960 году Ирвином Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon) - сотрудниками лаборатории Линкольна Массачусетского технологического института. Коды Рида-Соломона базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств. Первое массовое коммерческое применение коды Рида-Соломона получили в 1982 г. в компакт-дисках, в которых использовалось перемежение кодовых слов двух различных кодов Рида-Соломона. В дальнейшем коды Рида-Соломона стали широко применяться для исправления ошибок во многих системах, среди которых:
Метод мягкого декодирования, основанный на введении управления надежностью символов в процедуру списочного декодирования
Блок памяти 522 содержит 2т слов (2т - количество элементов конечного поля Галуа). Разрядность памяти - log2(tc+l). Слово памяти 522 сохраняет значение счётчика соответствующего значения . БПН работает в двух режимах. В 1-м режиме работы БПН осуществляет подсчёт различных значений . Поступающие на вход блока значения сохраняются в регистр 527. Счетчик в ячейке памяти 522, соответствующий этому значению , увеличивается на 1 схемой инкремента 523 и записывается в ту же ячейку памяти (блок вентилей 521 - открыт). Схема сравнения кодов 524 сравнивает значение текущего счетчика невязок со значением w и, если счетчик равен w, формирует сигнал обнаружения значения невязки , соответствующей искомой конфигурации ошибок.
Логический нуль на выходе элемента 528 формируется при активном сигнале Msk2 или неактивном сигнале разрешения работы Е. Тем самым блокируется инкрементирование количества на выходе памяти.
2-й режим работы (режим инициализации) задается сигналом / на 1-м входе блока подсчета невязок, при этом во все ячейки памяти 522 записываются нулевые слова. В режиме инициализации адреса ячеек памяти 522 поступают из местного устройства управления 560 через коммутатор 526. Блок вентилей 521 формирует нулевые слова на входе памяти 522. преобразования Фурье полинома A(2tc)(x) 420.1; модуля дискретного преобразования Фурье полинома B(2tc) (x) 420.2; коммутаторов 430.1 и 430.2; инвертора элементов поля Галуа 440; перемножителей элементов поля Галуа 450.1 и 450.2; умножителя на а 470.1; схемы возведения в куб элементов поля Галуа 470.2; регистра-защёлки 480, работающего по фронту тактового сигнала; двоичного счетчика номеров позиций принятого слова 490 с коэффициентом пересчета
МУУ 410 взаимодействует с процессором Галуа 300 и управляет блоком ДПФ 400. МУУ 410 накапливает возможные позиции ошибок веса tС, запоминая значения / в момент равенства нулю значения полинома
Схема 470.2 возводит в куб элементы поля Галуа, поступающие на ее первые входы, если на ее второй (управляющий) вход подается логическая 1; в противном случае она передает данные с ее первых входов на выходы без изменений.
Блок дискретного преобразования Фурье 400 работает в трёх режимах. Режим 0. При условии, что L2tС tС-1. В блок ДПФ загружаются только значения коэффициентов многочлена Л( (х) и ищутся позиции ошибок веса tС-\. Игнорируются сигналы на первых, четвертых- Функциональная схема модуля дискретного преобразования Фурье Режим 1. При условии, что управляющая переменная s 0. В блок ДПФ загружаются значения коэффициентов многочленов A(2tc)(x) и B(2tc) (x). Определяются коэффициенты Д. = a(2s+1) B(2tc) (a- )/rt2tc) (a- ) Для их вычисления перекрёстный коммутатор 430.1 работает в прямом направлении, подавая на вход инвертора 440 коэффициенты Л("). Если управляющая переменная s=0, схема возведения в куб 470.2 передает значения а1 со своих входов на выходы без изменения. Если s=1, то на выходе формируется значение азі (осуществляется возведение в куб). На пятом выходе БППФ значение Mskl (исключение уравнений из системы) формируется путем подачи через коммутатор 430.2 сигнала со второго выхода модуля дискретного преобразования Фурье 420.1, который имеет единичный уровень, когда Л()=0. Если s 0, одновременно осуществляется поиск позиций ошибок веса меньшего или равного tc.
Режим 2. При условии, что s 0. В блок ДПФ загружаются значения коэффициентов многочленов Л W и а W. Определяются коэффициенты R. = а( 2s 1)гЛ(2/с ) )/B (2tc(a ) Для их вычисления коммутатор 430.1 работает в перекрестном режиме, подавая на вход инвертора 440 значения В(1). Если управляющая переменная s=-1, схема возведения в куб 470.2 передает значения а1 со своих входов на выходы без изменения. Если s=-2, то на выходе формируется значение азі (осуществляется возведение в куб). На пятом выходе БДПФ значение Mskl формируется путем подачи через коммутатор 430.2 сигнала со второго выхода МДПФ 420.2 с единичным уровнем при В( )=0.
В каждом такте работы блока ДПФ 400 на первых выходах МДПФ полинома Л(х) 420.1 формируется значение Л(), на первых выходах МДПФ полинома В(х) 420.2 - значение на выходе регистра 480 - значение At. За время цикла работы блока ДПФ 400 / принимает значения из диапазона 0,… ,и-1. В 1-м и 2-м режимах А, Rt и Mskl записываются в БПК 550 БППО 500. Адреса памяти БППО 550 формируются с помощью счетчика 490. Значение счетчика 490 поступает на вход таблицы L, хранящейся в БСПС 600.
Оценка сложности устройства коррекции ошибок архивной оптической памяти
При условии, что управляющая переменная s 0. В блок ДПФ загружаются значения коэффициентов многочленов A(2tc)(x) и B(2tc) (x). Определяются коэффициенты Д. = a(2s+1) B(2tc) (a- )/rt2tc) (a- ) Для их вычисления перекрёстный коммутатор 430.1 работает в прямом направлении, подавая на вход инвертора 440 коэффициенты Л("). Если управляющая переменная s=0, схема возведения в куб 470.2 передает значения а1 со своих входов на выходы без изменения. Если s=1, то на выходе формируется значение азі (осуществляется возведение в куб). На пятом выходе БППФ значение Mskl (исключение уравнений из системы) формируется путем подачи через коммутатор 430.2 сигнала со второго выхода модуля дискретного преобразования Фурье 420.1, который имеет единичный уровень, когда Л()=0. Если s 0, одновременно осуществляется поиск позиций ошибок веса меньшего или равного tc.
Режим 2. При условии, что s 0. В блок ДПФ загружаются значения коэффициентов многочленов Л W и а W. Определяются коэффициенты R. = а( 2s 1)гЛ(2/с ) )/B (2tc(a ) Для их вычисления коммутатор 430.1 работает в перекрестном режиме, подавая на вход инвертора 440 значения В(1). Если управляющая переменная s=-1, схема возведения в куб 470.2 передает значения а1 со своих входов на выходы без изменения. Если s=-2, то на выходе формируется значение азі (осуществляется возведение в куб). На пятом выходе БДПФ значение Mskl формируется путем подачи через коммутатор 430.2 сигнала со второго выхода МДПФ 420.2 с единичным уровнем при В( )=0.
В каждом такте работы блока ДПФ 400 на первых выходах МДПФ полинома Л(х) 420.1 формируется значение Л(), на первых выходах МДПФ полинома В(х) 420.2 - значение на выходе регистра 480 - значение At. За время цикла работы блока ДПФ 400 / принимает значения из диапазона 0,… ,и-1. В 1-м и 2-м режимах А, Rt и Mskl записываются в БПК 550 БППО 500. Адреса памяти БППО 550 формируются с помощью счетчика 490. Значение счетчика 490 поступает на вход таблицы L, хранящейся в БСПС 600. 100 Функциональная схема МДПФ полинома A(2fc)(x) 420.1 представлена на рис. 3.10. МДПФ полинома B(2tc) (x) 420.2 реализуется по такой же схеме.
МДПФ 420 состоит из блока вентилей 421, регистров-защелок, работающих по фронту тактового импульса, 422.0 - 422.М-1, сумматора элементов поля Галуа на t+2 входа 423, селектора нулевого элемента поля Галуа 424, умножителей на постоянные коэффициенты в поле Галуа 425.1 - 425.Ґ+1, блоков логических элементов ИЛИ 426.1 - 426.Ґ+1.
Перед началом работы блока дискретного преобразования Фурье 400 в регистры 422.0 - 422.t+l записываются нули. Затем процессор Галуа 300 с помощью МУУ 410 загружает в эти регистры через блок вентилей 421 и блоки логических элементов ИЛИ 426.1 - 426.Ґ+1 коэффициенты многочлена A(2t) (x) ( B(2t) (x), x2B(2t) (x)). Сумма всех регистров 422.0 - 422.Ґ+1 дает значение многочлена в точке х=а0 на выходах сумматора элементов поля Галуа 423.
Далее значение каждого регистра 422.А: (k=1,…,t+1) соответственно умножается на с помощью умножителя на постоянные коэффициенты 425.к, где к - степень неизвестной при обрабатываемом в регистре коэффициенте многочлена. После этого сумма всех регистров 422.0 - 422.М-1 дает значение многочлена в точке х=а1.
Процесс повторяется до тех пор, пока не будет получено значение многочлена в точке х=а(п-1). В это время селектор нулевого элемента поля 424 формирует активный сигнал selO при обнаружении нулевого значения многочлена на выходах сумматора 423.
Аппаратная сложность разработанного устройства оценивалась в вентилях, необходимых для аппаратной реализации устройства, причем под вентилем понимается 2-входовой элемент И или ИЛИ с инверсиями на входе и/или выходе. Общая сложность устройства определялась как сумма сложностей всех составляющих его блоков и элементов. В таблице 3.1 дана сложность базовых элементов, используемых в устройстве коррекции ошибок. В таблице 3.1 m – разрядность элемента.
Устройство коррекции ошибок содержит буферную память данных 100, предназначенную для временного хранения принятых из канала символов исправляемых кодовых слов. Размер буферной памяти данных 100 равен 5n символам. Объем буферной памяти 100 можно рассчитать по следующей формуле:
Таким образом, разработанное устройства коррекции ошибок для архивных оптических дисков может быть реализовано на 35608 вентилях, при этом необходима память объемом 31744 бит.
Все блоки устройства коррекции ошибок (за исключением БППО при исправлении двух дополнительных ошибок) работают в темпе поступления символов в устройство и выполняют обработку принятого слова за время поступления очередного слова в устройство. При тактовой частоте 100 МГц пропускная способность устройства составит 100 Мбайт/с. Кодовые слова, содержащие 10 ошибок, встречаются редко и задержка БППО, существенная в этом случае, на общую производительность архивной оптической памяти практически не влияет.
Предложена структурно-функциональная организация устройства коррекции ошибок архивной оптической памяти, которая раскрывается через структурную схему устройства и функциональные схемы его основных блоков.
Выполнен синтез самого ресурсоемкого блока устройства – блока вычисления невязок, обеспечивший двукратное уменьшение объема его оборудования.
Предлагаемое устройство коррекции ошибок представляет собой синхронный потоковый декодер кодов Рида-Соломона, обрабатывающий входные данные в темпе их поступления.
Устройство реализует алгоритм мягкого декодирования ASE1F с радиусом декодирования t=10 для кодов Рида-Соломона с d=17, определенных над полем GF(28). Объем оборудования всего устройства коррекции ошибок может быть оценен в 35608 вентилей и 31744 бит оперативной памяти, что находится в пределах сложности современных декодеров помехоустойчивых кодов, используемых на практике. Пропускная способность устройства составляет 100 Мбайт/с (при тактовой частоте 100 МГц).
Выбор степени квантования информации о надежности символов кодового слова на входе устройства
С помощью программной модели было выполнено исследование эффективности коррекции ошибок разработанным декодером кода Рида-Соломона, реализующим алгоритм ASE1F.
В исследовании использовалась модель канала с Гауссовским шумом (AWGN) и модуляцией BPSK. В качестве меры надежности символа принималось минимальное значение модуля LLR составляющих символ бит.
На рис. 4.8 приведены результаты имитационного моделирования в виде графика зависимостей FER (Frame Error Ratio) от Eb/No для РС-кода (120, 104), используемого в архивных оптических накопителях информации.
Цифрами обозначены: 1 – классический декодер, исправляющий tC = 8 ошибок без использования мягких решений; 2 – декодер, реализующий алгоритм ASE1F с радиусом декодирования tC+1; 3 – тот же декодер с радиусом декодирования tC+2. Для экспериментального исследования устройства коррекции ошибок архивной Модель предусматривает генерацию тестовой псевдослучайной последовательности, моделирование источника ошибок информационного канала и моделирование алгоритмов мягкого декодирования кодов Рида-Соломона.
Исследование на программной модели показало, что при исправлении до 3-х дополнительных ошибок для РС-кода (120, 104) целесообразно квантовать информацию о надежности символов кодового слова 3 битами.
С помощью программной модели была произведена оценка эффективности коррекции ошибок устройством. Разработанное устройство обеспечивает снижение уровня ошибочных кадров (FER) в архивной оптической памяти в 12.6 раза (при FER=10-3).
В результате выполненного в диссертации комплекса исследований найдено решение актуальной научно-технической задачи повышения эффективности исправления ошибок, возникающих в каналах записи/воспроизведения накопителей архивной оптической памяти, за счет реализации мягкого декодирования с приемлемой аппаратной сложностью.
Основные результаты, полученные в диссертационной работе:
Проведен анализ существующих методов и устройств декодирования кодов Рида-Соломона. В результате данного анализа выявлены недостатки известных алгоритмов мягкого декодирования, главным из которых является высокая сложность, затрудняющая их реализацию в устройствах коррекции ошибок для архивной оптической памяти.
Предложен метод мягкого декодирования кодов Рида-Соломона, развивающий подход списочного декодирования путем введения в процедуру декодирования управления поиском позиций ошибок информацией о надежности принятых из канала символов. Дано теоретическое обоснование метода. Приведена формализация предлагаемого метода в виде процедуры декодирования кодов Рида-Соломона.
На основе предложенного метода разработано семейство алгоритмов мягкого декодирования кодов Рида-Соломона. Приведены результаты исследования их эффективности. Разработанные алгоритмы декодирования позволяют значительно повысить эффективность применения высокоскоростных кодов Рида-Соломона в системах хранения и передачи информации за счет исправления дополнительных ошибок. Например, алгоритм ASE1F обеспечивает дополнительный кодовый выигрыш по сравнению со стандартным декодированием около 0,42 dB. Эффективность алгоритма ASE1F выше, чем эффективность алгоритма Кеттера-Варди с мультиплисити 2.
Проведены исследования вычислительной сложности разработанного алгоритма мягкого декодирования кодов Рида-Соломона ASE1F. Вычислительная сложность алгоритма при исправлении одной дополнительной ошибки (t=9, =1) возрастает приблизительно в 1.5 раза относительно вычислительной сложности стандартного декодирования (t=8). При исправлении двух дополнительных ошибок (t=10, =2) вычислительная сложность алгоритма ASE1F увеличивается примерно в 4 раза (для Eb/No=6,5).
Предложена структурно-функциональная организация устройства коррекции ошибок архивной оптической памяти. Разработаны его структурная схема и функциональные схемы его основных блоков. Выполнен синтез самого ресурсоемкого блока устройства – блока вычисления невязок, обеспечивший двукратное уменьшение объема его оборудования. Объем оборудования всего устройства коррекции ошибок оценен в 35608 вентилей и 31744 бит оперативной памяти, что находится в пределах сложности современных декодеров помехоустойчивых кодов, используемых на практике.
В результате имитационного моделирования на ЭВМ устройства коррекции ошибок показано, что устройство обеспечивает снижение уровня ошибочных кадров (FER) в архивной оптической памяти в 12,6 раза. Основные технических решения, полученные в диссертации при разработке устройства коррекции ошибок архивной оптической памяти, защищены патентом РФ.
