Методи і засоби підвищення ефективності контролю помилок передачі та зберігання даних в комп`ютерних системах
DSpace at NTB NTUU KPI
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Методи і засоби підвищення ефективності контролю помилок передачі та зберігання даних в комп`ютерних системах
|
|
| Creator |
Турченко, Юрій Олександрович
|
|
| Description |
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - Національний технічний університет України "Київський політехнічний інститут", Київ, 2011. Дисертація присвячена проблемі підвищення ефективності виявлення та виправлення помилок при передачі та зберіганні даних в комп'ютерних системах шляхом розширення класу помилок, що гарантовано виявляються, а також прискорення обчислень, пов'язаних з контролем помилок. Запропоновано спосіб розширення класу помилок, що гарантовано виявляються за допомогою нелінійної зваженої контрольної суми. Для виявлення 4-х помилок при теоретично мінімальній кількості контрольних розрядів, цей спосіб передбачує формування компонент контрольної суми з використанням спеціального нелінійного булевого перетворення. Розроблено метод синтезу таких нелінійних булевих перетворень. Запропоновано і досліджено простий і ефективний підхід до корекції "пачки помилок", що виникають при передачі даних в лініях з імпульсно- кодовою модуляцією, а також при їх зберіганні на оптичних і магнітних дискових носіях комп'ютерних систем. Запропонований підхід до підвищення ефективності корекції "пачки помилок" передбачає розділення цієї задачі на дві: локалізацію спотворений бітів в "пачці помилок" та локалізацію в блоці даних біту, з якого починається "пачка". Для спрощення і зменшення обчислювальної складності при реалізації першої та другої з вказаних задач пропонується використання відповідно звичайної та зваженої контрольних сум. На основі запропонованого підходу розроблено два методи корекції однієї "пачки помилок". Один з них базується на використанні логічних операцій, а другий - арифметичних. Доведено, що застосування цих методів забезпечує зменшення складності обчислень, пов'язаних з виявленням та корекцією "пачки помилок" в порівнянні з кодами Ріда-Соломона, При цьому кількість контрольних розрядів при використанні арифметичних операцій - така ж сама, як і в кодах Ріда-Соломона і менша при використанні логічних операцій. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты.- Национальный технический университет Украины "Киевский политехнический институт". Киев, 2011. Диссертация посвящена проблеме повышения эффективности обнаружения и исправления ошибок, возникающих при передаче информации между компонентами компьютерных систем и при ее хранении на магнитных и оптических дисковых носителях путем расширения класса гарантированно обнаруживаемых ошибок, а также ускорения вычислений, связанных с контролем ошибок. Предложен способ расширения по сравнению с CRC класса ошибок, которые гарантированно обнаруживаются с использованием нелинейной взвешенной контрольной суммы. Способ гарантирует обнаружение 4-кратных ошибок передачи при использовании теоретически минимального числа контрольных разрядов. В качестве весовых коэффициентов битов предлагается использовать номер бита в блоке и результат нелинейного булевош преобразования над номером бита. Теоретически доказано, что для гарантированного обнаружения 4-кратных ошибок нелинейное булево преобразование должно обладать специфическими дифференциальными свойствами. Разработан формализованный метод синтеза нелинейных булевых преобразований, обладающих этими свойствами, а также программные средства для его реализации. Предложен и исследован простой и эффективный подход к коррекции одиночной "пачки ошибок" возникающей при передаче информации в линиях с импульсно-кодовой модуляцией и ее хранении на дисковых носителях компьютерных систем. Подход основан на раздельном решении двух задач: локализации искаженных битов в рамках "пачки ошибок" и локализации биты в блоке, с которого начинается "пачка ошибок". Для упрощения и снижения вычислительной сложности для реализации первой и второй задач предложено использовать соответственно обычную и взвешенную контрольные суммы. На основе предложенного общего подхода разработано два метода коррекции одиночной "пачки ошибок". Один из них использует логические, а второй - арифметические операции. Метод коррекции "пачки ошибок" на основе логических операций предполагает вычисление суммы по модулю символов, длина которых вдвое превышает максимальное число бит в "пачке". Это исключает возможность взаимного маскирования при суммировании искаженных битов и позволяет просто локализовать позиции искаженных битов в "пачке". Компонентами взвешенной контрольной суммы являются логические произведения битов блока на весовые коэффициенты, последовательность которых соответствует степеням конечного поля Галуа. Это позволило свести задачу локализации в блоке первого бита "пачки ошибок" к решению системы линейных булевых уравнений. Доказано, что реализация разработанного метода имеет на порядок меньшую вычислительную сложность по сравнению с решением аналогичной задачи с использованием кодов Рида-Соломона, при том, что в предложенном методе используется меньшее число контрольных разрядов. Коррекция "пачки ошибок" с использованием метода, основанного на арифметических операциях предполагает разделение блока на символы, длина которых соответствует максимальному числу бит в в "пачке" и использование трехкомпонептного контрольного кода: раздельно вычисляются суммы чисел с нечетными и нечетными порядковыми номерами в блоке, а также сумма арифметических произведений номера символа на его код. Арифметическое суммирование производится с учетом числа разрядов, на единицу большего, чем число бит в слагаемых - перенос за пределы этого числа игнорируется. Это позволило решить задачу коррекции "пачки ошибок" с таким же числом контрольных разрядов, как и в кодах Рида-Соломона. Первые две контрольные суммы позволяют локализовать позиции искаженных битов в "пачке". Определение номера символа, с которого начинается "пачка ошибок" сводится к операции арифметического деления, вычислительная сложность которой на порядки меньше авторегрессионного решения системы нелинейных уравнений, которое реализуется в кодах Рида-Соломона. Разработаны программные средства, реализующие предложенные методы коррекции одиночной "пачки ошибок". Теоретически и экспериментально доказано, что достигаемое в разработанных методах уменьшение вычисли- тельной и временной сложности по сравнению с кодами Рида-Соломона позволяет существенно упростить и ускорить выполнение контроля и исправления "пачки ошибок" возникающей при передаче информации и ее хранении на дисковых носителях компьютерных систем. Предложен подход к ускорению аппаратной реализации контроля ошибок передачи данных с использованием циклических избыточных кодов за счет эквивалентного представления результата виде взвешенной контрольной суммы со специально подобранными весовыми коэффициентами. Thesis for a Ph.D. degree by specialty 05.13.05 - Computer system and components. National Technical University of Ukraine "Kiev Polytechnic Institute", Kiev, 2011. Thesis is dedicated to a problem of increasing of efficiency of detecting and correcting of errors which appearances during transmission and storage in disk by expanding the class of guaranteed detecting errors and error control speed up. The way for expanding the class of guaranteed detecting errors by nonlinear weighed checksum has been proposed. For guaranteed detecting four errors by using of theoretical minimum control bits number the proposed way provide to checksum components forming by utilization of special nonlinear Boolean transformations. The method for synthesis of such transformations has been developed. This work investigates a simple and effective approach for the correction of errors that occur in bursts during data transmission in pulse-code modulation channels but also during data storage in magnetic and optical discs in computer systems. The suggested approach enhances the efficiency of single burst error control in low frequency channels and data storage, due to the decomposition of the main problem in two parts: the localization of the positions of the corrupted bits in the burst and the localization of the start point of the burst that has occurred. To succeed in reducing computational complexity and speeding up, the present technique suggests the use of a conventional checksum method and the use of the weighted version of the checksum for the solution of the first and the second problem respectively. Based of suggested approach two methods for correction of any single burst error has been developed. One of them based on logical operation utilization and another - arithmetical operation. It has been shown that the application of those methods lowers the computational cost of the operations that need to be executed for the correction of the burst error comparing to Reed - Solomon codes. The number on control bits therewith are equal to Reed - Solomon codes in use arithmetical operation and less in use logical operations. |
|
| Publisher |
НТУУ "КПІ"
|
|
| Date |
2011-04-11T10:52:45Z
2011-04-11T10:52:45Z 2011 |
|
| Type |
Thesis
|
|
| Identifier |
http://library.kpi.ua:8080/handle/123456789/839
|
|
| Language |
uk
|
|