Патент ссср 155820
Класс Н 04b; 21ат, 70т б 061; 42m, 14аз
G 06с; 74b, 8щ № 155820
СССР
Яф
Ъд
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СБЙДБТЕЛЬСТВУ
Подписная группа Л«174
Ю. М. Мартынов
СПОСОБ ПЕРЕДАЧИ ИНФОРМАЦИИ
Заявлего 3 гнолн 1969 -, за № 784915/26-"-1 в Комитет по делам изобретений и oT: ðûòètt при Совете 11и|и|стров СССР
Опубликовано в «Б|оллетене изобретений и товарных знаков» № 14 за 1963 г.
Известны способы передачи информации, позволяющие на приемном конце обнаруживать и исправлять ошибки, основанные на использовании кода Хаминга. Известны также способы исправления информации путем повторения выборки при условии, что существует обратная связь, по которой передается сигнал о наличии ошибок.
Основным недостатком подобных способов является брак кодового слова, в котором обнаружена ошибка. Даже при искажении одного-двух элементов приходится повторять всю и-элементную комбинацию (кодовое слово). В результате этого потери информации значительно превы. шают величину информации, вносимую каналом.
В предлагаемом способе объем повторно передаваемой информации при возникновении ошибки уменьшают путем передачи на передающий конец по каналу обратной связи всей информации, полученной в результате декодирования принятого кода. Основную информацию используют для формирования дополнительной — в виде разрядов кода, в которых возникла ошибка.
По описываемому способу в системе передачи информации с обратной связью по запросу передаются лишь дополнительные сведения, объем которых значительно меньше длины кодового слова и которых до=таточно, чтобы исправить ошибку.
¹ 155820
В качестве примера приведена система с простым девятиэлементным кодом, включающим пять информационных и четыре проверочных символов.
В табл. 1 представлен алгоритм кодирования; в табл. 2 даны двоичные номера элементов кодового слова.
Таблица 1
Состав группы проверки
Номер группы проверки
П
Ш
1, 3, 5, 9
2, 3, 6, 7
4, 5, 6
7, 8, 9
Таблица 2
Номер элемента порядковый двоичный порядковый двоичный
1001
0001
0011
0101 и
n — log. 1 C „) m. о
Для рассматриваемого примера m — 5, К = 2 и наименьшее значение, удовлетворяющее заданному неравенству, n = 12, т. с. можно получить
12 — log» (1 + 12 + бб) = 5,696 ) 5.
При кодировании пользуются четырьмя проверочными элементами.
Следовательно, три элемента можно употребить при передаче дополнительной информации. При безошибочном приеме кодового слова или в результате возникновения не обнаруживаемой кодом ошибки декодирующее устройство выдает нулевую четырехэлемептпую последовательность.
При наличии обнаруживаемой кодом ошибки результат декодирования отличается от нуля.
Рассмотрим канал, в котором для обеспечения заданной степени достоверности достаточно исправить одиночные и двойные ошибки. Для того чтобы исправить эти ошибки, необходимо передать дополнительное количество информации, минимум которого определяется по формуле:
¹ 155820
Возможные результаты декодирования и соответствующие им од:Iночные и двойные ошибки приведены в табл. 3.
Таблица 3
Результат декодирования
Возможные варианты ошибок
2 — 3
1 — 3
1 — 2
1 — 5
1 — 4
2 — 4
2 — 8
2 — 7
1 — 8
2 — 9
5 — 9
5 — 8
6 — 8
6 — 9
0001
0011
0101
1001
0111
1011
1101
1111
4 — 5
4 — 6
5 — 6
2 — 6
3 — 6
3 — 5
3 — 9
1 — 9
3 — 7
3 — 4
3 — 8
6 — 7
2
4
6
8
1 — 6
1 — 7
4 — 8
4 — 9
4 — 7
5 — 7
8 — 9
7 — 8
7 — 9
Если в результате декодирования возникает один из перечисленных номеров, например llll, то, следовательно, получается число двоичных единиц информации, определяемых соотношением
10g>IV — 1оо;У, = — 12 — 1о еЛ I, где n — длина кодового слова, Л, — число возможных вариантов ошибок, соответствующих полученному результату декодирования.
В рассматриваемом примере n — log 2 =- n — 1.
В наихудшем случае, при результатах декодирования 0001, 0010, 0011, количество полученной информации равно 9 — 2=7 двоичным единицам. Следовательно, достаточно повторить две двоичных единицы. чтобы раскрыть оставшуюся после приема неопределенность.
Для того чтобы получить дополняющую информацию, по обратному каналу передается результат декодирования, по которому при передаче осуществляется дополнительный анализ хранящегося кодового слова.
Для анализа используют лишь один элемент из пар ошибок, указанных в табл. 3. Так как при передаче дополняющей информации возможны ошиоки, то исправление будет правильным, если кратность ошибки че превысила исправляющей способности, обеспеченной введенной избыточностью (с учетом объема дополняющей информации). В дополняющей информации достаточно обнаружить одиночную ошибку, и если это произойдет, то необходимо исправить в кодовом слове один элемент, соответствующий данному результату декодирования, или любую пару, если отсутствует один элемент.
Если ошибки в дополняющей информации нет, то по той же программе, что и на передаче, производится дополнительньш контроль хранящегося принятого слова, в результате которого получается номер, соответствующий одному из искаженных элементов.
Передаем, например, кодовое слово 111101110, где элементы пронумерованы слева направо. Первый, второй, четвертый и восьмой — проверочные элементы, а третий, пятый, шестой, седьмой и девятый — шнрормационпые. Допустим, что в канале исказились пятый и седьмой элементы и принятое кодовое слово имеет вид 111111010. № 155820
В результате проверок на четкость получим последовательность
1111, которая будет передана источнику информации. Из табл. 3 следует, что достаточно обработать, например, седьмой и девятый элементы. Простейшая обработка заключается в том, что эти элементы и будут составлять дополняющую информацию. Таким образом, в канал будет передано сообщение 101, где третий элемент получен в результате суммирования по модулю 2 седьмого и девятого.
Если принятое сообщение не содержит ошибки, то сравниваются полученные вновь седьмой и девятый элементы с хранящимися в памяти. Так как не совпадает седьмой элемент, то необходимо исправить в кодовом слове еще и пятый элемент. После этого из кодового слова выделяют информационные элементы и передают потребителю.
Предмет изобретения
Способ передачи информации, основанный на использовании кода с обнарунсением ошибок и канала обратной связи, отличающийся тем, что, с целью уменьшения объема повторно передаваемой информаuHv npH aoaIti4rc>IoueHHH orzH6i Составитель В. Козлов Редактор Л. Герасимова Текред А. А, Камышиикова Корректор И. С, Дроздова Подп. к печ. 15/VII — 63 ". Формат бум. 70; 108 /, Объем 0,35 изд. л. Зак. 1874/4 Тираж 725 Цена 4 коп. ЦНИИПИ Государственного комитета по делам изобретений и открытий СССР Москва, Центр, пр. Серова, д. 4 Типография, пр. Сапунова, 2