СПОСОБ ОПРЕДЕЛЕНИЯ НАРУШЕНИЙ И ИСПРАВЛЕНИЯ НАРУШЕННЫХ КОДОВ РАЗРЯДОВ ЧИСЛА ПРИ КОДИРОВАНИИ "1 ИЗ 4"
METHOD OF DETERMINING VIOLATIONS AND CORRECTING VIOLATED CODES OF BIT POSITIONS IN "1 FROM 4" CODING

Изобретение относится к области вычислительной техники, техники связи и может быть использовано для построения вычислительных средств и средств связи в системах с повышенной достоверностью обрабатываемых данных, низким энергопотреблением, что в значительной мере сказывается на снижении массогабаритных характеристик данных систем.
Известно отказоустойчивое устройство (патент РФ №2297036, МПК G06F 11/08, заявлено 20.05.2004, опубликовано 10.11.2005), обеспечивающее передачу информации, закодированной по способу двумерного итеративного кода, позволяющее корректировать ошибки в одном байте информации и обнаруживать их в остальных байтах.
Недостатками устройства (способа кодирования) являются недостаточная достоверность обрабатываемой и передаваемой информации и неравномерность потребления электроэнергии в процессе работы.
7
Наиболее близким по технической сущности прототипом к заявляемому способу является способ передачи дискретной информации (патент РФ №2239941, МПК Н03М 13/00, заявлено 19.12.2002, опубликовано 10.11.2004).
На передающем конце линии связи способ предусматривает наличие источника информации, кодирующего устройства и передатчика, а на приемном - приемника, устройства контроля (декодирующего устройства) и оконечного устройства.
Данные с источника информации поступают в кодирующее устройство, подвергаются в нем преобразованию - информационные разряды обрамляются контрольными и передатчиком транслируются в приемную часть канала.
Приемник осуществляет прием закодированной информации и передает ее в устройство контроля (декодирующее устройство).
Устройство контроля проверяет поступившую информацию на отсутствие ошибок, при их наличии осуществляет коррекцию принятой информации (устраняет ошибки) и передает ее в оконечное устройство для дальнейшей обработки. Поскольку устройство контроля не всегда обеспечивает исправление ошибок, то при отсутствии такой возможности, оно фиксирует их наличие.
Необходимо отметить, что состав передаваемой информации (количество единиц в двоичном числе) не является постоянными и величина потребляемой электроэнергии, которая напрямую зависит от состава обрабатываемой информации, должна рассчитываться на ее максимальное значение.
Способу - прототипу присущи недостатки отказоустойчивого устройства, указанного выше.
Задачей, на решение которой направлено предлагаемое техническое решение, является повышение достоверности передаваемой информации и снижение уровня потребления электроэнергии.
Это достигается тем, что в известном способе передачи дискретной информации в кодирующем устройстве передающей стороны информация, поступившая из источника в двоичном коде, преобразуется в код «1 из 4» с активным нулем. Важной особенностью системы кодирования «1 из 4» является прозрачная связь с двоичной системой, которая реализуется простыми схемами. Для наглядности приведем таблицу соответствия двух разрядов двоичной системы и системы «1 из 4» с активным нулем:
№ п/п
Двоичная система
Система «1 из 4»
1
00
0001
2
01
0010
3
10
0100
4
11
1000
1
2
2
Преобразованная информация формируется в виде массива слов, который можно представить в форме таблицы, содержащей П строк (слов), каждая из которых содержит П четверичных разрядов в коде «1 из 4», при этом одноименные четверичные разряды строк образуют П вертикальных столбца массива.
r
в
У каждого слова массива формируется контрольный код (K) путем последовательного суммирования разрядов слова без учета переноса, а у каждого вертикального столбца аналогичным способом формируется контрольный код (K) одноименных вертикальных разрядов.
Подготовленный (закодированный) к передаче массив имеет вид (см. фиг.1) и в таком формате поступает на приемную часть канала передачи информации.
ri
вi
В устройстве контроля (декодирующем устройстве) принятая от приемника информация проверяется на соответствие коду «1 из 4» и контрольным кодам K и K, и при обнаружении ошибки в принятой информации определяется характер ошибки, ее местоположение в массиве.
Заключительной операцией в устройстве контроля является устранение ошибки - восстановление принятой информации.
Предлагаемый способ исправления нарушений кодов разрядов числа при кодировании «1 из 4» заключается в следующем.
ro
во
Схемой контроля определяется четверичный разряд, в котором произошло нарушение кода «1 из 4». Содержимое этого разряда заменяется нулевым кодом (0001) и у полученного вспомогательного числа определяется контрольный код (K и К), полученный последовательным суммированием разрядов числа без учета переноса.
Далее определяется разность контрольного кода исходного числа и контрольного кода вспомогательного числа:
r
ro
r
в
во
в
K-K=ΔK или К-К=ΔК
r
в
Для восстановления нарушенного кода четверичного разряда ранее установленный нулевой код в данном разряде заменяется на ΔK (ΔК).
Приведенный способ назовем «способом нулевого кода».
r
в
После восстановления нарушенного кода разряда производится проверка числа на совпадение исходного контрольного кода с контрольным кодом исправленного числа. При ΔK (ΔK)=0 операция восстановления выполнена.
ri
вi
Рассмотренный способ исправления кодов в одном четверичном разряде слова или столбца применим и при неоднократных ошибках в четверичных разрядах слов и столбцов. Предположим, что массив информации, поступивший в устройство контроля, содержит восемь слов и десять вертикальных столбцов и каждое слово и столбец сопровождается контрольными кодами (K и К), как показано на рисунке (см. фиг.2).
ij
22
24
Каждый четверичный разряд массива (P) имеет свой номер Р, где i - номер слова в массиве, a j - номер столбца. Пусть заштрихованные разряды (например, Р, P и т.д.) не соответствуют требованиям кода «1 из 4».
Исправление кодов осуществляется в следующей последовательности этапов:
47
72)
1 - корректируются слова, имеющие искажение в одном четверичном разряде (Р, P;
25
59
2 - корректируются столбцы, имеющие искажение в одном четверичном разряде (Р, Р);
54
3 - корректируется слово, имеющее после этапа 2 искажение в одном четверичном разряде (Р);
22
4 - корректируется столбец, имеющий после этапа 1 искажение в одном четверичном разряде (Р);
24
5 - корректируется слово, имеющее после этапа 4 искажение в одном четверичном разряде (Р).
Операция восстановления информации выполнена.
Рассмотренный способ исправления искажений в четверичных разрядах применим и в случаях, когда искажения не нарушают принципа кодирования «1 из 4», то есть в четверичном разряде имеет место двойная ошибка. К примеру, вместо кода 010 или вместо кода 0001 - код 0100. Способ сравнения принятого контрольного кода со сформированным при приеме будет фиксировать их несовпадение, однако неисправный четверичный разряд будет неизвестен.
Использование вертикальных столбцов массива и их контрольных кодов определяет этот разряд. И действительно, каждый четверичный разряд массива одновременно принадлежит только одному слову и только одному вертикальному столбцу этого массива. А поскольку номер вертикального столбца определяется номером четверичного разряда слова, то номер вертикального столбца, в котором не совпали контрольные коды, определит нам и номер неисправного четверичного разряда слова.
Приведенный способ определения нарушений и исправления нарушенных кодов разрядов числа при кодировании «1 из 4» в значительной мере повышает достоверность передаваемой информации.
При этом следует отметить, что способ выявляет все ошибки, но не все возможные комбинации ошибок подлежат коррекции.
-6
Доля неисправляемых ошибок незначительна. Например, для массива из десяти слов, каждое из которых содержит сто разрядов, доля неисправляемых ошибок составляет примерно 6×10.
29
Вариант невозможности исправления ошибки можно рассмотреть на примере. Если предположить существование ошибки в разряде Р, то восстановить информацию во втором и пятом словах невозможно.
При создании вычислительных средств и средств связи использование способа кодирования «1 из 4» по сравнению с двоичной системой кодирования при равной достоверности их функционирования снижает уровень энергопотребления в 5-5,5 раза.
Сущность изобретения поясняется фиг.1, 2, 3.
На фиг.1 представлена структура массива слов, сформированного для передачи по линии связи.
На фиг.2 представлена, как пример, структура массива, поступившего в приемную часть линии связи.
На фиг.3 обозначены:
1 - источник информации;
2 - кодирующее устройство;
3 - передатчик;
4 - приемник;
5 - устройство контроля;
6 - оконечное устройство.
Предлагаемый способ определения и исправления нарушений при обмене информацией, существующая элементная база (микропроцессоры и контроллеры, реализованные на базовых БИС) дают возможность создания разнообразных вычислительных средств и средств связи для построения управляющих систем реального времени, одной из основных характеристик которых является высокий уровень достоверности обрабатываемой информации (исправления ошибок при передаче информации).