Підвищення ефективності засобів виявлення та виправлення помилок в послідовних інтерфейсах комп’ютерних систем

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ З ТЕМОЮ ДИСЕРАТАЦІЇ

1. Мулки Ахмед Яссин Ал Бадайнех. Исправление ошибок с использованием дифференциально-кодированной суммы // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2005.-№ 43.- С.64-72.

2. Самофалов К.Г. Марковский А.П., Мулки Ахмед Яссин Ал Бадайнех. Обнаружение и исправление ошибок передачи данных с использованием взвешенных контрольных сумм // Проблеми інформатизації та управління. Збірник наукових праць.- К.:НАУ.- 2008.- Випуск 3(14).- С.121-128. (Дисертантом запропоновано підхід до підвищення ефективності виявлення двократних помилок за рахунок зменшення кількості контрольних розрядів, а також спосіб виправлення виявлених помилок шляхом часткової повторної передачі блоку, виконано аналіз ефективності запропонованого способу виправлення помилок ).

3. Марковский А.П., Мулки Ахмед Яссин Ал Бадайнех, Пуя Солеймани Нежадиан. Об одном подходе к повышению эффективности обнаружения и исправления ошибок передачи данных // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2007.-№ 47.- С.62-74 (Дисертантом запропоновано вдосконалення способу виявлення та виправлення помилок за допомогою двовимірної контрольної суми, зокрема застосування зваженої контрольної суми в стовпцях матриці даних, що контролюється, а також виконано аналіз ефективності вдосконаленого способу).

4. Алі Тауфік Окла Аль-Хавальді, Мулки Ахмед Яссин Ал Бадайнех, Антоненко А.А. Об одном подходе к повышению надежности обнаружения ошибок передачи данных методов контрольных сумм // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2006.-№ 45.- С.27-35 (Дисертантом запропоновано спосіб виявлення помилок, зумовлених порушеннями синхронізації за рахунок спеціальних зважених контрольних сум).

5. Мнацаканов А.В., Мулки Ахмед Яссин Ал Бадайнех, Варяник А.И. Алгоритм синтеза упорядочивающего хеш-преобразования для постоянного массива ключей // Вісник Національного технічного університету України ”КПІ”. Інформатика, управління та обчислювальна техніка.- К.:ВЕК+.- 2004.-№ 42.- С.188-197 (Дисертантом запропоновано технологію виправлення багатократних помилок з використанням постійної хеш-пам'яті).

6. Марковський О.П., Мулки Ахмед Яссин Ал Бадайнех, Корниец Е.В. Обнаружение многократных ошибок передачи данных с использованием контрольной суммы // Труды 8-й международной научно-технической конференции ”Современные информационные и электронные технологии”, 21-27 травня 2007 р. -2007.-С.193. (Дисертантом запропоновано підхід до вибору вагових коефіцієнтів зваженої контрольної суми для гарантованого виявлення помилок парної кратності, більшої за два).

АНОТАЦІЇ

Мулкі Ахмед Ясін Ал Бадайнех. Підвищення ефективності засобів виявлення та виправлення помилок в послідовних інтерфейсах комп'ютерних систем. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - Національний технічний університет України ”Київський політехнічний інститут”, Київ, 2008.

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

Для розширення класу помилок, що гарантовано виявляються та класу помилок, що виправляються без повторної передачі запропоновано використання зваженої двовимірної контрольної суми. Розроблено алгоритм виявлення та корекції помилок. Показано, що запропонована технологія забезпечує більшу ефективність виявлення та виправлення помилок в порівнянні з CRC і традиційною двовимірною контрольною сумою.

Запропоновано новий спосіб для гарантованого виявлення помилок в асинхронних каналах передачі даних комп'ютерних систем. В каналах такого типу домінують помилки синхронізації. Запропонований спосіб має за основу використання зважених контрольних сум і дозволяє, на відміну від CRC гарантовано виявляти однократні та багатократні помилки синхронізації.

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

Для зменшення об'єму даних, що пересилаються повторно для виправлення виявлених помилок, запропоновано спосіб, оснований на використанні зважених контрольних сум.

Ключові слова: виявлення помилок, корекція помилок, кодування помилок, зважені контрольні суми, циклічні надлишкові коди, послідовні інтерфейси комп'ютерних систем.

Мулки Ахмед Яссин Ал Бадайнех. Повышение эффективности обнаружения и исправления ошибок в последовательных интерфейсах компьютерных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты.- Национальный технический университет Украины ”Киевский политехнический институт”, Киев, 2008.

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

Для расширения класса гарантированно обнаруживаемых ошибок и класса ошибок, исправляемых без повторной передачи предложено использовать модификацию двумерной контрольной суммы. Модификация состоит в том, что для контроля по столбцам проверяемой матрицы данных используется взвешенная контрольная сумма, что уменьшает вероятность взаимного маскирования ошибок. Разработан формализированный алгоритм обнаружения и коррекции ошибок. Показано, что предложенная технология обеспечивает большую эффективность обнаружения и исправления ошибок по сравнению с CRC и традиционной двумерной контрольной суммой, в частности, класс гарантированно обнаруживаемых ошибок расширен до 7-ми кратных, а исправляемых без повторной передачи - до 3-х кратных. Доказано, что предложенная модификация двумерной контрольной суммы обеспечивает гарантированное обнаружение ”пачек” ошибок.

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

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

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

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

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

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

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

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

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

Mulki Ahmеd Yasseen Al Badaenih. Increasing the efficiency of means for error detection and correction in serial interfaces of computer systems. - Manuscript.

Thesis for a Ph.D. degree by specialty 05.13.05 - Computer system and components.

National Technical University of Ukraine “Kiev Polytechnic Institute”, Kiev, 2008.

Thesis is dedicated to a problem of increasing of efficiency of error detecting and correcting in serial interfaces of computers systems by expanding the class of guaranteed detecting errors and by decreasing the information content which is repeatedly transmit for detected error correction.

For solving the problem of expanding the class of guaranteed detecting errors and class of ones which can be corrected without repeat transmission the utilization of two-dimension weighed check sum has been proposed. Algorithm for error detection and correction has been worked out. It has been shown that proposed techniques ensure superior data transformation error detecting and correcting effectiveness in compare to CRC and traditional two-dimension checksum.

The new approach for guaranteed detecting errors in asynchronous data transmission channels of computer systems has been proposed. In such type of channel the timing error dominate. The proposed approach is based on weighed checksum utilization and allowed to guaranteed detecting of single and multiple timing errors in distinction to CRC.

A new techniques for increasing the effectiveness of checksum multiple errors detection in serial computer interface with spectrum modulation by decreasing of number of check bits has been proposed.

Key words: error detecting, error correction, coding errors, weighted checksums, cyclic redundancy checking, computer serial interface.

Размещено на Allbest.ru