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

i; Президиум ВАК России ¡¡ ¿ ■ ■ -

| ¿решедаа т

Й а$>йеудил ученую степень ДОК1 'OPA |

II ,

T-TSIWK"

'Начальник управления ВАК России

Пензенский государственный технический университет

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

Савельев Борис Александрович

Повышение качества хранения информации на оптических ЗУ

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

Д и с с е р т а ц ия

на соискание ученой степени доктора технических наук

Пенза 1997

ВВЕДЕНИЕ

СОДЕРЖАНИЕ

8

ГЛАВА 1. ИССЛЕДОВАНИЕ НОВОЙ КАСКАДНОЙ СИСТЕМЫ

КОДИРОВАНИЯ ДЛЯ ОПТИЧЕСКИХ ЗУ 24 1.1. Разработка каскадной системы кодирования

на основе канальных кодов 27

1.2.1. Способы преобразования и формирования

сигналов в кодах типа (п, и/2) 31

1.2.2. Способы преобразования и формирования сигналов

в кодах типа к В п Тр для систем передачи 34

1.2.3. Теоретическая оценка корректирующих свойств

каскадных кодов на основе канальных кодов типа (п, и/2) 36

1.3.1. Способы преобразования в канальных кодах типа (п, к) 40

1.3.2. Теоретическая оценка корректирующих свойств каскадных

кодов на основе кодов типа (п, к) 43

1.4.1. Способы преобразования в канальных кодах типа (1 гшп 1 тазе) 48

1.4.2.Теорегическая оценка корректирующих свойств

неравномерных кодов типа (1 т1П -1 та*) 50 1.5. Теоретическая оценка корректирующих свойств

каскадных кодов на основе кодов типа (щ-то)/то 52

1.6. Разработка декодера внутреннего кода 55

1.6.1. Адаптивная регистрация принимаемых сигналов 55

1.6.2. Разработка схемы декодера внутреннего кода 59 Выводы к главе 1 64

ГЛАВА 2. АНАЛИЗ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ ПЗУ §5

2.1.1. Последовательное умножение / деление 65

2.1.2. Оценка параметров устройства умножения / деления 68

2.2.1. Разработка устройства параллельного вычисления 69

2.2.2. Оценка параметров устройства вычисления 71 2.3.1. Ступенчатая схема умножения / деления 72

2.3.2. Оценка параметров устройства умножения / деления 75

Выводы к главе 2 76

ГЛАВА 3. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВЫЧИСЛЕНИЙ В

ПОЛИНОМИАЛЬНОМ БАЗИСЕ 77

3.1. Анализ процессов умножения в полиномиальном базисе 77

3.2.1. Оптимизация параллельного умножителя типа S-HS 80

3.2.2 . Оценка параметров умножителя типа S-HS 83

3.3.1. Разработка параллельного умножителя типа И-S-S 86

3.3.2. Оценка параметров умножителя 89 Выводы к главе 3 95

ГЛАВА 4. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ И РАЗРАБОТКА

ВЫЧИСЛИТЕЛЕЙ В НОРМАЛЬНОМ БАЗИСЕ 95 4.1. Теоретическое обоснование процессов

генерации нормальных базисов 96

4.2 .Разработка устройства умножения за m тактов 101

4.3.1. Разработка параллельного умножителя типа S - И - S (схема 1) 108

4.3.2. Оценка параметров умножителя 112

4.4.1. Разработка параллельного умножителя типа S - И - S (схема 2) 115

4.4.2. Оценка параметров умножителя 123

4.5.1. Разработка параллельного умножителя типа И- S (схема 1) 127

4.5.2. Оценка параметров умножителя 128

4.6.1. Разработка параллельного умножителя типа И - S ( схема 2 ) 130

4.6.2. Оценка параметров умножителя 130

4.7.1. Разработка параллельного умножителя типа И - S ( схема 3 ) 132

4.7.2. Оценка параметров умножителя 134 Выводы к главе 4 136

ГЛАВА 5. ПРОЕКТИРОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМЫ

КОДИРОВАНИЯ ВНЕШНИМИ КОДАМИ

138

5.1. Анализ основных этапов процессов кодирования 138

5.2Л1роектирование конструкции внешнего декодера 140

5.3.1. Конструкция устройства для вычисления

компонент Si 148

5.3.2. Оценка параметров устройства 149 5. 4.1. Проектирование конструкции спецпроцессора

для вычисления Xj , j\ и Еч 150

5.4.2. Оптимизация объема вычислений 153

5.4.3. Оценка параметров спецпроцессора 159

5.5.1. Проектирование конструкции спецпроцессора для вычисления локаторов ошибок 162

5.5.2. Оценка параметров спецпроцессора 168 Выводы к главе 5 170

ГЛАВА 6. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ПАРАМЕТРОВ СИСТЕМ

ДЕКОДИРОВАНИЯ НА СИСТОЛИЧЕСКИХ СТРУКТУРАХ 173

6.1. Декодирование по модернизированному алгоритму Берлекэмпа - Месси 175

6.1.1. Анализ конструкции блоков для решения ключевого уравнения 177

6.1.2. Оценка параметров блоков декодера 180

6.2. Декодирование по модернизированному алгоритму Евклида (вариант 1) 185

6.2.1. Анализ конструкции системы декодирования 185

6.2.2. Оценка параметров системы декодирования 194

6.3. Декодирование по алгоритму Евклида ( вариант 2 ) 202

6.3.1. Анализ конструкции ячейки для вычисления Л(х) и Q(x) 203

6.3.2. Оценка параметров ячейки 205 6. 4 . Декодирование с исправлением стираний и

использованием алг оритма Евклида ( вариант 3 ) 207

6.4.1. Анализ конструкции системы декодирования 208

6.4.2. Оценка параметров системы декодирования 210

6.5. Декодирование с использованием алгоритма Евклида ( вариант 4 ) 215

6.5.1. Анализ конструкции основных блоков системы декодирования 216

6.5.2. Оценка параметров системы декодирования 218

6.6. Декодирование во временной области ( вариант 1 ) 221

6.6.1. Анализ системы декодирования по алгоритму Блейхута 222.

6.6.2. Оценка параметров системы декодирования 225

6.?. Декодирование во временной области с регулярной структурой

( вариант 2 ) 229

6.7.1. Анализ конструкции систем ы декодирования 231

6.7.2. Оценка параметров системы декодирования 233 Выводы к главе 6 235

ГЛАВА 7. АНАЛИТИЧЕСКИЕ И ЭКПЕРИМЕНТАЛЬНЫЕ

ИССЛЕДОВАНИЯ ИСКАЖЕНИЙ НА ОПТИЧЕСКИХ ЗУ И

СИСТЕМ ИХ КОРРЕКЦИИ 239

7.1. Анализ помехоустойчивости сигналов считывания 239

7.1.1. Помехоустойчивость накопителей с однократной записью 240

7.1.2. Помехоустойчивость накопителей с фазовым переходом 241

7.1.3. Помехоустойчивость магнитооптических накопителей

с перпендикулярной записью 242

7.2. Анализ дефектности оптических дисков 244

7.2.1. Статистика дефектов оптических дисков 244

7.2.2. Вероятностные характеристики дефектности носителей 246

7.2.3. Расчет вероятности ошибок 248

7.3. Исследования систем декодирования при группировании ошибок 250

7.3.1. Выбор математической модели потока ошибок на выходе оптического ЗУ 251

7.3.2. Моделирование процессов перемещения кодовых блоков 252

7.3.3. Моделирование процессов декодирования матричными кодами 255

7.3.4. Моделирование матричного кодирования с перемежением символов 260

7.3.5. Моделирование многопроходовой коррекции ошибок 262 Выводы к главе 7 269

ЗАКЛЮЧЕНИЕ

271

ЛИТЕРАТУРА 274

ПРИЛОЖЕНИЕ А.

К главе 1 290 Таблица АЛ. Комбинации кода (10,8) с не более чем одним нулем по

краям 291

А1. Моделирование работы декодера (2-7) 294

Таблица А.2. Разрешенные комбинации канального кода 2/9 301

Таблица А.З. Разрешенные комбинации канального кода 4/9 302

ПРИЛОЖЕНИЕ В .

К главе 2 305 В1. Сложность типовых узлов системы помехоустойчивого

кодирования 306

Таблица В. 1. Элементы поля Галуа , пораждаемые 308 д(х)=: х8 + х7 ч х5 + х3 + 1

ПРИЛОЖЕНИЕ С .

К главе 4 313

Т аблица СЛ. Представление элем ентов для поля вР (25) 314 Таблица С.2. Ведущие элементы циклотомических классов,

генерирующие нормальные базисы 315

Таблица С.З. Элементы нормального базиса поля 316 вР(23 ),д(х) = х8 + х7 + х5 + х3 + 1

Таблица С.4. Таблица нормальных базисов 318

Таблица С.З. Параметры умножителя для 327 ОР(28) (ё(х) = х8+х7 + х5+х3+1)

ПРИЛОЖЕНИЕ В.

К главе 5 328

Таблица В. 1 329

ПРИЛОЖЕНИЕ Е.

К главе 6 330

Таблица В. 1. Параметры декодера для частотной области 331

ПРИЛОЖЕНИЕ Р.

К главе 7 332

Р1. Моделирование и выбор модели потока ошибок для каналов считывания оптических ЗУ 333

Интервальные модели 333

Пакетные модели 338

¥2. Моделирование процессов коррекции искажений матричным кодом РС 342

ПРИЛОЖЕНИЕ в. Акты внедрения в производство результатов исследований 349

ПРИЛОЖЕНИЕ Н. Акты внедрения в производство изобретений 359

Введение

Широкое применение средств хранения информации связано с бурным развитием вычислительных средств, в частности, баз данных и знаний. В настоящее время основу ЗУ составляют носители на магнитной основе: ленты, диски, пластины /113/. Однако уже сейчас их существенно потеснили накопители на оптических носителях /120,123,128/.

Это связанно с такими достоинствами оптических накопителей:

- возможность хранения огромных массивов информации (например, от 1-г4 Гбайт на одном диске и до 1013 байт в накопительной системе для NASA) /117/;

- низкая стоимость хранения информации - стоимость хранения на магнитной ленте составила в среднем около 0,02 доллара/Мбайт в 1984 г., в перспективе для оптических накопителей может быть снижена до 0,002 доллара/Мбайт;

-возможность хранения записанной информации без перезаписи в 5-И0 раз дольше, чем на магнитной ленте. Если оптимальный период перезаписи на ленте равен 6 месяцам, то для оптических дисковых накопителей обеспечивается надежное хранение информации без перезаписи не менее 10 лет.

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

Для дальнейшего повышения плотности применяется вертикальная запись в магнитном слое с игольчатыми пигментами или 8-ферритами. Оптимистические предположения дают прогноз на увеличение плотности записи на магнитных носителях до 10000 изменений потока на дюйм /113/.

Более высокая плотность записи достигается на оптических ЗУ. С применением полупроводниковых лазеров приходят к плотности записи в 5 раз выше, а газовых лазеров - в 15 раз выше, чем на магнитных ЗУ. Современные оптические ЗУ на постоянной основе обеспечивают плотность записи 0,4 -tIjlik на бит и расстояние между дорожками 0,6 4-1,2 juk /134/.

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

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

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

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

Согласно имеющимся данным, вероятность ошибки при считывании с магнитных носителей равна МО-5-МО"6 на бит. Как показано ниже, большинство выпускаемых в настоящее время средств коррекции исправляют независимые ошибки и многократные пачки ошибок, вероятность появления которых составляет для реальных оптических дисковых ЗУ (ОДЗУ) 1-Ю"4 -1-10~5,

Достоверность информации и надежность средств повышения ее характеризуют качество хранения информации. Как показано в работах Дружинина Г.В. /24,25/ и конференциях " Качество информации", это определение включает многие характеристики. При оценке качества хранения информации в своих исследованиях мы будем пользоваться такими характеристиками: достоверность, оцениваемую остаточной вероятностью ошибок Рост(п) и вероятностью необнаружения ошибок Рно( п), быстродействие, сложность, обьем вычислений и регулярность средств коррекции, где п - длина кодового блока.

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

растают благодаря продолжающемуся увеличению плотности БИС и снижению их стоимости в сочетании с более уточненными методами исправления ошибок.

Существенное развитие получила теория помехоустойчивого кодирования. В большой степени оно явилось результатом широкого применения помехоустойчивых кодов практически во всех областях техники, включая передачу данных, космическую связь, шифрование, хранение и обработку данных. Фундаментальные результаты опубликованы в монографиях и многочисленных статьях и патентах. Здесь отметим работы российских ученых Зиновьева В.А. / 28,29/ и Зяблова В. В. /10,11/ по обобщенным каскадным кодам, Кузнецова A.B. /39, 40/ и Сагаловича Ю. JI. /83,84/ по коррекции ошибок и дефектов в оперативных ЗУ, а также зарубежных ученых по алгебраической теории кодирования: Берлекэмпа Э. /6/, Блейхута Р. / 7 /, Галлагера Р. / 18/, Касами Т. / 94/, Мак- Вильяме / 49/, Питерсона У. / 57/, Форни Д. / 97/.

В части теоретических результатов, которые способствовали широкому применению кодов в системах передачи и накопителях отметим работы по каскадным кодам /27, 29, 31, 97/. Эти коды обеспечивают получение конечной скорости передачи при больших длинах кодов.

С увеличением плотности записи растет и скорость записи/считывания информации. Чтобы не снижать скорость считывания данных с накопителя исправление искажений должно проводиться в реальном масштабе времени. Поэтому актуальна разработка эффективных алгоритмов декодирования. До недавнего времени при декодировании кодов Рида - Соломона (PC) использовались алгоритмы Питерсона и Берлекэмпа - Месси /18, 57/. Однако сейчас широко применяются и исследуются новые алгоритмы, в частности алгоритм Уэлша - Берлекэмпа, модифицированный алгоритм Берлекэмпа - Месси, алгоритмы Евклида, алгоритм Арамбеполы - Чомнеза / 107 /.

Эти алгоритмы работают в частотной или временной областях и обеспечивают высокую скорость декодирования. Часть из них повышает регулярность структуры декодеров, что является важным фактором при построении кодеров и декодеров в виде БИС.

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

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

готовления. В последние годы остаточная вероятность ошибок нормировалась величиной 1 • 1 СГУ на бит, сейчас это во многих случаях неприемлемо /113/.

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

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

Важное значение также имеет контроль результатов исправления искажений ( под искажениями мы будем понимать ошибки и стирания). Это весьма существенно, поскольку в результате исправления появляются новые необнаруженные ошибки. Вот некоторые случаи появления их /113/:

-возникновение необнаруженных ошибок при декодировании;

- необнаружение ошибок обнаруживающим или исправляющим ошибки кодом;

- отказ синхронизации в системах без защиты синхросигналов от ошибок;

- нерегулярный отказ в незащищенном буфере при чтении или записи;

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

-сбои в аппаратных средствах.

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

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

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

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