способ передачи дискретного сообщения и система для его осуществления

Формула изобретения

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

Y_n = X_kG,

где Х_k - вектор-строка исходного сообщения из k информационных элементов;

Y_n - вектор-строка кодированного сообщения из k информационных и m проверочных элементов, m - наименьшее целое число не меньше, чем log₂n, n= k+m;

G - порождающая матрица операций из k строк и n столбцов, составленная из матрицы размером kхk с операциями g⁰ на диагонали и операциями g¹ на прочих местах и приписанной к ней справа дополнительной матрицы размером kхm, неповторяющиеся строки которой представляют собой последовательности операций g¹ и g⁰ или операций g¹ и g², выбранные из возможных последовательностей, включающих не более (m-2) операций g¹, или матрица, полученная из порождающей матрицы операций перестановкой столбцов и/или строк;

- операция обобщенного матричного умножения по правилу:

y_j = g^v_ij(x_i) при jk,

y_j = g²[g^v_ij(x_i)] при j>k,

если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или по правилу:

y_i = g^v_ij(x_i),

если строки дополнительной матрицы представляют собой последовательности операций g¹ и g², где у_i - j-й элемент вектора-строки кодированного сообщения;

g^v_ij(x_i) = g^v_ij(x₁)g^v_2j(x₂) ...g^v_kj(x_k);

- операция суммирования элементов абелевой группы;

g_ij ^v(х_i) - операция g^v над элементом х_i по правилу ij-го элемента матрицы;

v= [0,2] , i= [1, k] , j= [1, n] ,



е - единичный элемент абелевой группы,

декодирование демодулированного сообщения Y"_n производят путем исключения из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций Н, содержащим по одной операции g⁰, при условии наличия не более одного элемента, не равного е, в векторе-столбце S_m ^T, образованном по правилу:



где Y"_n ^Т - транспонированный вектор-строка Y"_n;

Н - проверочная матрица операций размером mхn, образованная путем транспонирования дополнительной матрицы, приписывания к ней справа матрицы размером mxm с операциями ⁰ на диагонали и операциями g¹ на прочих местах и перестановки столбцов, идентичной перестановке столбцов порождающей матрицы операций, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или тем же путем с заменой операций g² на g⁰, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g².

2. Способ передачи дискретного сообщения по п. 1, отличающийся тем, что при равенстве между собой всех элементов вектора-столбца S_m ^T, не равных е, и совпадении вектора-столбца S_m ^T, преобразованного путем замены в нем этих элементов на операцию g⁰, а прочих элементов - на операцию g¹, с j-м столбцом матрицы Н изменяют значение j-го символа вектора строки Y"_n путем его сложения с элементом, обратным одному из элементов вектора-столбца S_m ^T, не равных е.

3. Способ передачи дискретного сообщения по п. 1 или 2, отличающийся тем, что при условии принадлежности элементов сообщения кольцу с единицей операция g⁰ является умножением на единицу, операция g¹ - умножением на ноль, операция g² - умножением на минус единицу.

4. Способ передачи дискретного сообщения по любому из пп. 1-3, отличающийся тем, что при условии принадлежности элементов сообщения кольцу классов вычетов по модулю q, где q - натуральное число, является операцией сложения по модулю q.

5. Система передачи дискретного сообщения из элементов аддитивной абелевой группы, включающая размещенные на передающей стороне последовательно соединенные кодер, вход которого является входом системы, модулятор и передатчик и размещенные на приемной стороне последовательно соединенные приемник, демодулятор и декодер, выход которого является выходом неисправляемого сообщения системы, отличающаяся тем, что кодер выполнен в виде, реализующем алгоритм:

Y_n = X_kG,

где Х_k - вектор-строка исходного сообщения из k информационных элементов;

Y_n - вектор-строка кодированного сообщения из k информационных и m проверочных элементов, m - наименьшее целое число не меньше, чем log₂n, n= k+m;

G - порождающая матрица операций из k строк и n столбцов, составленная из матрицы размером kxk с операциями g⁰ на диагонали и операциями g¹ на прочих местах и приписанной к ней справа дополнительной матрицы размером kxm, неповторяющиеся строки которой представляют собой последовательности операций g¹ и g⁰ или операций g¹ и g², выбранные из возможных последовательностей, включающих не более (m-2)операций g¹, или матрица, полученная из порождающей матрицы операций перестановкой столбцов и/или строк;

- операция обобщенного матричного умножения по правилу:

y_j = g^v_ij(x_i) при jk,

y_j = g²[g^v_ij(x_i)] при j>k,

если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или по правилу:

y_i = g^v_ij(x_i),

если строки дополнительной матрицы представляют собой последовательности операций g¹ и g²,

где у_i - j-й элемент вектора-строки кодированного сообщения,

g^v_ij(x_i) = g^v_ij(x₁)g^v_2j(x₂) ...g^v_kj(x_k),

- операция суммирования элементов абелевой группы;

g_ij ^v(х_i) - операция g^v над элементом х_i по правилу ij-го элемента матрицы,

v= [0,2] , i= [1, k] , j= [1, n] ,



е - единичный элемент абелевой группы,

декодер выполнен в виде, обеспечивающем исключение из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций Н, содержащим по одной операции g⁰, при условии наличия не более одного элемента, не равного е, в векторе-столбце S_m ^T, образованном по правилу:



где Y"_n ^Т - транспонированный вектор-строка Y"_n;

Н - проверочная матрица операций размером mxn, образованная путем транспонирования дополнительной матрицы, приписывания к ней справа матрицы размером mxm с операциями ⁰ на диагонали и операциями g¹ на прочих местах и перестановки столбцов, идентичной перестановке столбцов порождающей матрицы операций, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или тем же путем с заменой операций g² на g⁰, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g².

6. Система передачи дискретного сообщения по п. 5, отличающаяся тем, что декодер выполнен в виде, обеспечивающем перед исключением из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций Н, исправление значения j-го символа вектора-строки Y"_n путем его сложения с элементом, обратным одному из элементов вектора-столбца S_m ^Т, не равных е, при равенстве между собой всех элементов вектора-столбца S_m ^Т, не равных е, и совпадении вектора-столбца S_m ^Т, преобразованного путем замены в нем этих элементов на операцию g⁰, а прочих элементов - на операцию g¹, с j-м столбцом проверочной матрицы операций Н.

7. Система передачи дискретного сообщения по п. 5 или 6, отличающаяся тем, что кодер содержит первый блок оперативной памяти, k выходов которого соединены с соответствующими первыми k информационными входами второго блока оперативной памяти, выход которого является выходом кодера, блок памяти кодов операций порождающей матрицы операций, первую группу из m вычислителей проверочного элемента, входы управления алгоритмом вычисления которых соединены с соответствующими m выходами блока памяти кодов операций порождающей матрицы операций, m вычислителей функции g², включенные между соответствующими выходами первой группы из m вычислителей проверочного элемента и соответствующими с (k+1)-го по n-й информационными входами второго блока оперативной памяти, последовательно соединенные первый формирователь импульсов и первый кольцевой счетчик до k, информационный выход которого соединен со входом адреса строки матрицы блока памяти кодов операций порождающей матрицы операций, а выход переполнения - со входами обнуления первого блока оперативной памяти и первой группы из m вычислителей проверочного элемента, последовательно соединенные генератор импульсов с частотой повторения fn/k, первый ключ и первый кольцевой счетчик до n, информационный выход которого соединен с адресным входом второго блока оперативной памяти, первый элемент И, выход которого соединен с управляющим входом первого ключа, первый триггер, выход которого соединен с прямым входом первого элемента И, инвертирующий вход которого соединен с выходом переполнения первого кольцевого счетчика до n и входом сброса первого триггера, последовательно соединенные первый удвоитель частоты повторения импульсов, вход которого соединен с выходом генератора импульсов с частотой повторения fn/k, и кольцевой счетчик до (2k+1), выход переполнения которого соединен со счетным входом первого триггера, объединенные информационные входы первого блока оперативной памяти и вычислителей проверочного элемента первой группы из m вычислителей проверочного элемента, вход запуска формирователя импульсов и вход синхронизации генератора импульсов с частотой повторения fn/k являются входом кодера, f - частота повторения элементов дискретного сообщения.

8. Система передачи дискретного сообщения по любому из пп. 5-7, отличающаяся тем, что декодер содержит третий блок оперативной памяти, n выходов которого соединены с соответствующими n информационными входами четвертого блока оперативной памяти, выход которого является выходом неисправляемого сообщения декодера, блок памяти кодов операций проверочной матрицы матрицы операций, вторую группу из m вычислителей проверочного элемента, входы управления алгоритмом вычисления которых соединены с соответствующими m выходами блока памяти кодов операций проверочной матрицы операций, последовательно соединенные второй формирователь импульсов и второй кольцевой счетчик до n, информационный выход которого соединен с адресным входом блока памяти кодов операций проверочной матрицы операций, а выход переполнения - со входами обнуления третьего блока оперативной памяти и вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, последовательно соединенные генератор импульсов с частотой повторения fk/n, второй ключ, второй кольцевой счетчик до k и третий ключ, информационный выход которого соединен с адресным входом четвертого блока оперативной памяти, блок принятия решения о декодировании, m входов которого соединены с выходами соответствующих вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, а выход - с управляющим входом третьего ключа, второй элемент И, выход которого соединен с управляющим входом второго ключа, второй триггер, выход которого соединен с прямым входом второго элемента И, инвертирующий вход которого соединен с выходом переполнения второго кольцевого счетчика до k и входом сброса второго триггера, последовательно соединенные второй удвоитель частоты повторения импульсов, вход которого соединен с выходом генератора импульсов с частотой повторения fk/n, и кольцевой счетчик до [(2(k+1)+1] , выход переполнения которого соединен со счетным входом второго триггера, объединенные информационные входы третьего блока оперативной памяти и вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, вход запуска второго формирователя импульсов и вход синхронизации генератора импульсов с частотой повторения fk/n являются входом декодера.

9. Система передачи дискретного сообщения по п. 8, отличающаяся тем, что выход блока принятия решения о декодировании соединен с управляющим входом третьего ключа через первый элемент ИЛИ, введены блок принятия решения об исправлении ошибок, выход которого соединен со вторым входом первого элемента ИЛИ, последовательно соединенные вычислитель ошибки, вход запуска которого соединен с выходом блока принятия решения об исправлении ошибки, а тактовый вход - с выходом переполнения второго кольцевого счетчика до k, вычислитель функции g² и сумматор элементов абелевой группы, второй вход которого соединен с выходом четвертого блока оперативной памяти, а выход является выходом исправляемого сообщения декодера, m входов блока принятия решения об исправлении ошибки и m входов вычислителя ошибки соединены с выходами соответствующих вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента.

10. Система передачи дискретного сообщения по любому из пп. 7-9, отличающаяся тем, что вычислитель проверочного элемента содержит последовательно соединенные четвертый ключ, вычислитель функции g¹, второй элемент ИЛИ, накапливающий сумматор элементов абелевой группы, выход которого соединен с его вторым входом, и пятый ключ, управляющий вход которого является входом обнуления, выход - выходом вычислителя проверочного элемента, шестой ключ, выход которого соединен со вторым входом первого элемента ИЛИ, дешифратор, вход которого является входом управления алгоритмом вычисления вычислителя проверочного элемента, а выходы соединены с управляющими входами соответственно четвертого и шестого ключей, объединенные информационные входы которых являются информационным входом вычислителя проверочного элемента.

Описание изобретения к патенту

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

Известен способ передачи дискретного сообщения из элементов аддитивной абелевой группы, включающий последовательные кодирование дискретного сообщения, его модуляцию, передачу в канал связи, демодуляцию принятого сигнала и его декодирование [1] .

Известна система передачи дискретного сообщения из элементов аддитивной абелевой группы, включающая размещенные на передающей стороне последовательно соединенные кодер, модулятор и передатчик и размещенные на приемной стороне последовательно соединенные приемник, демодулятор и декодер [1] .

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

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

Указанный технический результат достигается тем, что в способе передачи дискретного сообщения из элементов аддитивной абелевой группы, включающем последовательное кодирование сообщения, его модуляцию, передачу сообщения в канал связи, демодуляцию принятого сигнала и его декодирование, кодирование производят по правилу:

Y_n = X_kG,

где X_k - вектор-строка исходного сообщения из k информационных элементов,

Y_n - вектор-строка кодированного сообщения из k информационных и m проверочных элементов, m - наименьшее целое число, не меньшее, чем log₂n, n = k+m,

G - порождающая матрица операций из k строк и n столбцов, составленная из матрицы размером kxk с операциями g⁰ на диагонали и операциями g¹ на прочих местах и приписанной к ней справа дополнительной матрицы размером kxm, неповторяющиеся строки которой представляют собой последовательности операций g¹ и g⁰ или операций g¹ и g², выбранные из возможных последовательностей, включающих не более (m-2) операций g¹, или матрица, полученная из порождающей матрицы операций перестановкой столбцов и/или строк,

- операция обобщенного матричного умножения по правилу: y_j = g^v_ij(x_i) при jk, y_j = g²[g^v_ij(x_i)] при j>k, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или по правилу: y_i = g^v_ij(x_i), если строки дополнительной матрицы представляют собой последовательности операций g¹ и g², где

y_j-j-й элемент вектора-строки кодированного сообщения,

g^v_ij(x_i) = g^v_ij(x₁)g^v_2j(x₂) ...g^v_kj(x_k),

- операция суммирования элементов абелевой группы,

g^v _ij(x_i) - операция g^v над элементом х_i по правилу ij-го элемента матрицы, v = [0, 2] , i= [1, k] , j= [1, n] ,



e - единичный элемент абелевой группы,

декодирование сообщения Y"_n производят путем исключения из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций H, содержащим по одной операции g⁰, при условии наличия не более одного элемента, не равного e, в векторе-столбце S^Т _m, образованном по правилу:



где Y"_n ^Т - транспонированный вектор-строка Y"_n,

H - проверочная матрица операций размером mxn, образованная путем транспонирования дополнительной матрицы, приписывания к ней справа матрицы размером mхm с операциями ⁰ на диагонали и операциями g¹ на прочих местах и перестановки столбцов, идентичной перестановке столбцов порождающей матрицы операций, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или тем же путем с заменой операций g² на g⁰, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g².

Указанный технический результат достигается также тем, что перед исключением из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций H, при равенстве между собой всех элементов вектора-столбца S^Т _m, не равных е, и совпадении вектора-столбца S^Т _m, преобразованного путем замены в нем этих элементов на операцию g⁰, а прочих элементов - на операцию g¹, c j-м столбцом матрицы H изменяют значение j-го символа вектора-строки Y"_n путем его сложения с элементом, обратным одному из элементов вектора-столбца S^Т _m, не равных е.

Указанный технический результат достигается также тем, что при условии принадлежности элементов сообщения кольцу с единицей операция g⁰ является умножением на единицу, операция g¹ - умножением на ноль, операция g² - умножением на минус единицу.

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

Указанный технический результат достигается также тем, что в системе передачи дискретного сообщения из элементов аддитивной абелевой группы, включающей размещенные на передающей стороне последовательно соединенные кодер, вход которого является входом системы, модулятор и передатчик и размещенные на приемной стороне последовательно соединенные приемник, демодулятор и декодер, выход которого является выходом некорректируемого сообщения системы, кодер выполнен в виде, реализующем алгоритм:

Y_n = X_kG,

где X_k - вектор-строка исходного сообщения из k информационных элементов,

Y_n - вектор-строка кодированного сообщения из k информационных и m проверочных элементов, m - наименьшее целое число, не меньшее, чем log₂ n, n = k+m,

G - порождающая матрица операций из k строк и n столбцов, составленная из матрицы размером kxk с операциями g⁰ на диагонали и операциями g¹ на прочих местах и приписанной к ней справа дополнительной матрицы размером kxm, неповторяющиеся строки которой представляют собой последовательности операций g¹ и g⁰ или операций g¹ и g², выбранные из возможных последовательностей, включающих не более (m-2) операций g¹, или матрица, полученная из порождающей матрицы операций перестановкой столбцов и/или строк,

- операция обобщенного матричного умножения по правилу: y_j = g^v_ij(x_i) при jk, y_j = g²[g^v_ij(x_i)] при j>k, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или по правилу: y_i = g^v_ij(x_i), если строки дополнительной матрицы представляют собой последовательности операций g¹ и g², где

y_j - j-й элемент вектора-строки кодированного сообщения,

g^v_ij(x_i) = g^v_ij(x₁)g^v_2j(x₂) ...g^v_kj(x_k),

- операция суммирования элементов абелевой группы,

g^v _ij(x_i) - операция g^v над элементом x_i по правилу ij-го элемента матрицы,

v = [0,2] , i= [1, k] , j= [1, n] .

e - единичный элемент абелевой группы,

декодер выполнен в виде, обеспечивающем исключение из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций H, содержащим по одной операции g⁰, при условии наличия не более одного элемента, не равного е, в векторе-столбце S^Т _m, образованном по правилу:



где Y"_n ^Т - транспонированный вектор-строка Y"_n,

H - проверочная матрица операций размером mxn, образованная путем транспонирования дополнительной матрицы, приписывания к ней справа матрицы размером mxm с операциями ⁰ на диагонали и операциями g¹ на прочих местах и перестановки столбцов, идентичной перестановке столбцов порождающей матрицы операций, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или тем же путем с заменой операций g² на g⁰, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g².

Указанный технический результат достигается также тем, что декодер выполнен в виде, обеспечивающем перед исключением из вектора-строки Y"_n элементов, соответствующих по номеру столбцам проверочной матрицы операций H, исправление значения j-гo символа вектора-строки Y"_n путем его сложения с элементом, обратным одному из элементов вектора-столбца S^Т _m, не равных е, при равенстве между собой всех элементов вектора-столбца S^Т _m, не равных е, и совпадении вектора-столбца S^Т _m, преобразованного путем замены в нем этих элементов на операцию g⁰, а прочих элементов - на операцию g¹, c j-м столбцом проверочной матрицы операций H.

Указанный технический результат достигается также тем, что кодер содержит первый блок оперативной памяти, k выходов которого соединены с соответствующими первыми k информационными входами второго блока оперативной памяти, выход которого является выходом кодера, блок памяти кодов операций порождающей матрицы операций, первую группу из m вычислителей проверочного элемента, входы управления алгоритмом вычисления которых соединены с соответствующими m выходами блока памяти кодов операций порождающей матрицы операций, m вычислителей функции g², включенные между соответствующими выходами первой группы из m вычислителей проверочного элемента и соответствующими с (k+1)-го по n-й информационными входами второго блока оперативной памяти, последовательно соединенные первый формирователь импульсов и первый кольцевой счетчик до k, информационный выход которого соединен со входом адреса строки матрицы блока памяти кодов операций порождающей матрицы операций, а выход переполнения - со входами обнуления первого блока оперативной памяти и первой группы из m вычислителей проверочного элемента, последовательно соединенные генератор импульсов с частотой повторения fn/k, первый ключ и первый кольцевой счетчик до n, информационный выход которого соединен с адресным входом второго блока оперативной памяти, первый элемент И, выход которого соединен с управляющим входом первого ключа, первый триггер, выход которого соединен с прямым входом первого элемента И, инвертирующий вход которого соединен с выходом переполнения первого кольцевого счетчика до n и входом сброса первого триггера, последовательно соединенные первый удвоитель частоты повторения импульсов, вход которого соединен с выходом генератора импульсов с частотой повторения fn/k, и кольцевой счетчик до (2k+1), выход переполнения которого соединен со счетным входом первого триггера, объединенные информационные входы первого блока оперативной памяти и вычислителей проверочного элемента первой группы из m вычислителей проверочного элемента, вход запуска формирователя импульсов и вход синхронизации генератора импульсов с частотой повторения fn/k являются входом кодера, f - частота повторения элементов дискретного сообщения.

Указанный технический результат достигается также тем, что декодер содержит третий блок оперативной памяти, n выходов которого соединены с соответствующими n информационными входами четвертого блока оперативной памяти, выход которого является выходом неисправляемого сообщения декодера, блок памяти кодов операций проверочной матрицы операций, вторую группу из m вычислителей проверочного элемента, входы управления алгоритмом вычисления которых соединены с соответствующими m выходами блока памяти кодов операций проверочной матрицы операций, последовательно соединенные второй формирователь импульсов и второй кольцевой счетчик до n, информационный выход которого соединен с адресным входом блока памяти кодов операций проверочной матрицы операций, а выход переполнения - со входами обнуления третьего блока оперативной памяти и вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, последовательно соединенные генератор импульсов с частотой повторения fk/n, второй ключ, второй кольцевой счетчик до k и третий ключ, информационный выход которого соединен с адресным входом четвертого блока оперативной памяти, блок принятия решения о декодировании, m входов которого соединены с выходами соответствующих вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, а выход - с управляющим входом третьего ключа, второй элемент И, выход которого соединен с управляющим входом второго ключа, второй триггер, выход которого соединен с прямым входом второго элемента И, инвертирующий вход которого соединен с выходом переполнения второго кольцевого счетчика до k и входом сброса второго триггера, последовательно соединенные второй удвоитель частоты повторения импульсов, вход которого соединен с выходом генератора импульсов с частотой повторения fk/n, и кольцевой счетчик до [(2(k+1)+1] , выход переполнения которого соединен со счетным входом второго триггера, объединенные информационные входы третьего блока оперативной памяти и вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента, вход запуска второго формирователя импульсов и вход синхронизации генератора импульсов с частотой повторения fk/n являются входом декодера.

Указанный технический результат достигается также тем, что выход блока принятия решения о декодировании соединен с управляющим входом третьего ключа через первый элемент ИЛИ, введены блок принятия решения об исправлении ошибки, выход которого соединен со вторым входом первого элемента ИЛИ, последовательно соединенные вычислитель ошибки, вход запуска которого соединен с выходом блока принятия решения об исправлении ошибки, а тактовый вход - с выходом переполнения второго кольцевого счетчика до k, вычислитель функции g² и сумматор элементов абелевой группы, второй вход которого соединен с выходом четвертого блока оперативной памяти, а выход является выходом исправляемого сообщения декодера, m входов блока принятия решения об исправлении ошибки и m входов вычислителя ошибки соединены с выходами соответствующих вычислителей проверочного элемента второй группы из m вычислителей проверочного элемента.

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

На фиг. 1 приведен пример кодирования и декодирования конкретного сообщения, на фиг. 2 изображена функциональная электрическая схема системы передачи дискретного сообщения, на фиг. 3 - функциональная электрическая схема кодера, на фиг. 4 - функциональная электрическая схема декодера, на фиг. 5 - функциональная электрическая схема вычислителя проверочного элемента.

Система передачи дискретного сообщения содержит кодер 1, модулятор 2, передатчик 3, приемник 4, демодулятор 5, декодер 6.

Кодер 1 содержит первый формирователь 7 импульсов, блок памяти 8 кодов операций дополнительной матрицы, генератор 9 импульсов с частотой повторения fn/k, первый удвоитель 10 частоты повторения импульсов, первый кольцевой счетчик 11 до k, первую группу из m вычислителей 12 проверочного элемента, первый ключ 13, кольцевой счетчик 14 до (2k+1), первый элемент И 15, первый блок оперативной памяти 16, m вычислителей 17 функции g², первый триггер 18, второй блок оперативной памяти 19, первый кольцевой счетчик 20 до n.

Декодер 6 содержит второй формирователь 21 импульсов, блок памяти 22 кодов операций проверочной матрицы операций, генератор 23 импульсов с частотой повторения fk/(k+1), второй удвоитель 24 частоты повторения импульсов, второй кольцевой счетчик 25 до n, вторую группу из m вычислителей 26 проверочного элемента, второй ключ 27, кольцевой счетчик 28 до [2(k+1)+1] , третий блок оперативной памяти 29, блок принятия решения 30 о декодировании, блок принятия решения 31 об исправлении ошибки, вычислитель 32 ошибки, второй элемент И 33, первый элемент ИЛИ 34, (m+1)-й вычислитель 35 функции g², второй триггер 36, четвертый блок оперативной памяти 37, третий ключ 38, второй кольцевой счетчик 39 до k, сумматор 40 элементов абелевой группы.

Вычислитель 12(26) содержит четвертый ключ 41, дешифратор 42, шестой ключ 43, вычислитель 44 функции g¹, второй элемент ИЛИ 45, накапливающий сумматор 46 элементов абелевой группы, пятый ключ 47.

Способ передачи дискретного сообщения осуществляют следующим образом.

Формируют порождающую матрицу операций из k строк и n столбцов, составленную из матрицы размером kxk с операциями ⁰ на диагонали и операциями g¹ на прочих местах и приписанной к ней справа дополнительной матрицы размером kxm, неповторяющиеся строки которой представляют собой последовательности операций g¹ и g⁰ или операций g¹ и g², выбранные из возможных последовательностей, включающих не более (m-2) операций g¹. Возможно и использование порождающей матрицы операций, полученной из указанной порождающей матрицы операций перестановкой столбцов и/или строк. Полученная порождающая матрица операций представляет собой матрицу, составленную в отличие от обычной матрицы не из чисел, а из указаний, предписывающих проведение определенной операции при взаимодействии с данным элементом порождающей матрицы операций.

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

Дискретное сообщение X_k кодируют путем обобщенного матричного умножения вектора-строки X_k на сформированную порождающую матрицу операций G.

Процедура вновь введенной здесь операции обобщенного матричного умножения схожа с процедурой обычного матричного умножения, поскольку ее выполняют в том же порядке, а именно: осуществляют парные операции взаимодействия между i-м элементом вектора-строки X_k и каждым ij-м (лежащим на пересечении i-й строки и j-гo столбца) элементом матрицы операций G, а затем суммируют результаты всех i операций, получая в результате j-й элемент вектора-строки Y_n. При этом каждая из упомянутых здесь операций, выполнение которых необходимо для реализации операции обобщенного матричного умножения, представляют собой операции суммирования по правилам, установленным для элементов той абелевой группы [2, с. 140] , которой принадлежат элементы сформированного источником дискретного сообщения X_k из k информационных элементов. Операции g^v (g⁰, g¹ и g²) являются операциями суммирования с единичным элементом группы [2, с. 139] , суммирования с обратным элементом группы [2, с. 140] и двукратного суммирования с обратным элементом группы соответственно.

Кодированное сообщение модулируют и передают в канал связи.

Принятое сообщение демодулируют, а затем декодируют путем обобщенного матричного умножения проверочной матрицы операций H на транспонированный вектор-строку Y"_n ^Т.

Проверочную матрицу операций H размером mxn формируют путем транспонирования дополнительной матрицы, приписывания к ней справа матрицы размером mxm с операциями g⁰ на диагонали и операциями g¹ на прочих местах, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g⁰, или тем же путем с заменой операций g² на g⁰, если строки дополнительной матрицы представляют собой последовательности операций g¹ и g² и (если формирование порождающей матрицы операций производилось с перестановкой столбцов) перестановкой столбцов, идентичной перестановке столбцов порождающей матрицы операций.

Анализируя полученный в результате декодирования вектор-столбец S^Т _m, принимают решение об отсутствии ошибки и при наличии в векторе- столбце S^Т _m не более одного элемента, не равного единичному элементу группы, исключают из вектора-строки Y"_n элементы, соответствующие по номеру столбцам проверочной матрицы, содержащим по одной операции g⁰, отбрасывая тем самым проверочные элементы, введенные в сообщение при кодировании.

Если в векторе-столбце S^Т _m обнаружены равные между собой элементы, каждый из которых не равен единичному элементу группы, это означает, что в принятом сообщении имеется одна ошибка, которую исправляют. Для этого заменяют в векторе-столбце S^Т _m единичные элементы на операцию g¹, остальные - на операцию g⁰. Затем сравнивают полученный в результате замены вектор-столбец S^Т _m со столбцами матрицы H и определяют номер ее столбца, совпавшего с вектором-столбцом S^Т _m, и делают вывод о наличии ошибки в символе вектора-строки Y"_n, имеющем тот же номер, что и столбец матрицы H, совпавший с преобразованным вектором-столбцом S^Т _m. Исправление ошибки производят путем сложения ошибочного символа вектора-строки Y"_n с элементом, обратным любому из элементов вектора-столбца S^Т _m, не равных единичному элементу группы (поскольку в этом случае все элементы вектора-столбца S^Т _m, не равные единичному элементу группы, будут равны между собой).

Если элементы сообщения принадлежат кольцу с единицей, являющемуся частным случаем аддитивной абелевой группы, то операция g⁰ вырождается в операцию умножения на единицу, операция g¹ - в операцию умножения на ноль, а операция g² - в операцию умножения на минус единицу.

Если элементы сообщения принадлежат кольцу классов вычетов по модулю q, являющемуся частным случаем кольца с единицей, то вырождается в операцию сложения по модулю q.

На (фиг. 1) приведен конкретный пример передачи сообщения X_k, состоящего из 4 цифр. Построена порождающая матрица G по указанному выше правилу. Проверочные столбцы поставлены на первое, второе и четвертое места. После обобщенного матричного умножения вектора-строки X_k на матрицу G получен вектор-строка кодированного сообщения _n, содержащий проверочные символы на первом, втором и четвертом местах.

Демодулированное сообщение Y"_n принято с ошибкой в 5-й позиции. Поэтому результатом обобщенного матричного умножения проверочной матрицы H на транспонированный вектор-строку Y"_n ^Т явился вектор-столбец S^T _m, совпадающий с 5-м столбцом проверочной матрицы H, и было произведено декодирование путем отбрасывания проверочных элементов, т. е. выделения элементов исходного сообщения, и изменения 5-го элемента путем его сложения с элементом, обратным одному из неединичных элементов вектора-столбца S^Т _m.

Система передачи дискретного сообщения работает следующим образом.

Каждый элемент сформированного источником дискретного сообщения X_k, состоящего из следующих одно за другим кодовых слов, длиной k элементов каждое, поступив на вход кодера 1, попадает на информационные входы первого блока оперативной памяти 16 и первой группы вычислителей 12, запускает первый формирователь 7 и синхронизирует генератор 9. Импульс с выхода первого формирователя 7 запускает первый кольцевой счетчик 11. Пока первый кольцевой счетчик 11 производит подсчет поступающих на его вход импульсов, элементы кодового слова запоминаются в соответствующих ячейках первого блока оперативной памяти 16. Каждый импульс, подсчитанный счетчиком 11, переносит набор кодов операций соответствующей строки дополнительной матрицы из блока памяти 8 на входы управления алгоритмом вычисления первой группы вычислителей 12. Эти коды в каждом вычислителе 12 попадают на входы дешифраторов 42. В зависимости от кода операции, поступившего на дешифратор 42, он открывает четвертый ключ, пропуская элемент кодового слова на вход накапливающего сумматора 46, где он преобразуется по правилу g², поступая затем на первый вход второго элемента ИЛИ, или шестой ключ, пропуская элемент кодового слова на второй вход второго элемента ИЛИ и далее - на вход накапливающего сумматора 46. В накапливающем сумматоре 46 каждый последующий элемент суммируется с суммой предыдущих по правилу суммирования элементов абелевой группы, образуя проверочный элемент. После поступления k-го элемента кодового слова на вход первого кольцевого счетчика 11 на его выходе переполнения появляется импульс, который, обнуляя первый блок оперативной памяти 16, переносит информацию с выходов первого блока оперативной памяти 16 в первые k ячеек памяти второго блока оперативной памяти 19 и, попав на входы обнуления первой группы из m вычислителей 12, открывает в каждом из них пятый ключ 47, пропуская полученные суммы на вычислители 17, где полученные значения проверочных элементов преобразуются по правилу g² и записываются в ячейки памяти с (k+1)-й по n-ю второго блока оперативной памяти 19. Импульсы с выхода генератора 9 с частотой повторения, в (k+1)/k раз превышающей частоту повторения элементов кодового слова, поступают на информационный вход второго ключа 13, который, будучи изначально в запертом состоянии, не пропускает их на вход первого кольцевого счетчика 20. Эти же импульсы приходят на вход первого удвоителя 10, увеличивающего в 2 раза частоту повторения поступающих импульсов, и с его выхода - на вход кольцевого счетчика 14. С приходом (2k+1)-гo импульса (приблизительно посередине промежутка времени между моментами прихода на вход кодера 1 последнего элемента текущего и первого элемента следующего за ним кодового слова) на вход кольцевого счетчика 14 с его выхода переполнения поступает импульс на счетный вход первого триггера 18, опрокидывая его. Образовавшееся на выходе первого триггера 18 напряжение "логической единицы" передается на прямой вход первого элемента И 15. Поскольку первый кольцевой счетчик 20 еще не начал счет, на его выходе переполнения будет сохраняться напряжение "логического нуля" и, следовательно, на выходе первого элемента И 15 появится напряжение "логической единицы", открывающее второй ключ 13. Импульсы с выхода генератора 9 станут поступать на вход первого кольцевого счетчика 20, в результате чего на его информационном выходе появится код, сменяющийся с каждым вновь подсчитанным импульсом. Этот код, попав на адресный вход второго блока оперативной памяти 19, будет инициировать сброс информации из его ячейки, имеющей тот же порядковый номер, что и импульс, подсчитанный первым кольцевым счетчиком 20, и k информационных и m проверочных элементов кодового слова будут последовательно переданы на вход модулятора 2. После поступления n-го импульса на вход первого кольцевого счетчика 20 на его выходе переполнения появится напряжение "логической единицы", которое сбросит первый триггер 18, и на выходе первого элемента И 15 появится напряжение "логического нуля", закрывающее первый ключ 13 и прекращающее поступление импульсов с выхода генератора 9 на вход второго кольцевого счетчика 20, подготавливая его к следующему циклу работы.

Модулированное сообщение с выхода модулятора 2 поступает на вход передатчика 3 и направляется в канал связи.

Принятое сообщение, пройдя через приемник 4, демодулируется в демодуляторе 5 и поступает на вход декодера 6.

Каждый элемент принятого кодового слова, поступив на вход декодера 6, попадает на информационные входы третьего блока оперативной памяти 29 и второй группы вычислителей 26, запускает второй формирователь 21 и синхронизирует генератор 23. Импульс с выхода второго формирователя импульсов 21 запускает второй кольцевой счетчик 25. Пока второй кольцевой счетчик 25 производит подсчет поступающих на его вход импульсов, элементы кодового слова запоминаются в соответствующих ячейках третьего блока оперативной памяти 29. Каждый импульс, подсчитанный счетчиком 25, переносит набор кодов операций соответствующего столбца проверочной матрицы операций из блока памяти 22 на входы управления алгоритмом вычисления второй группы вычислителей 26. Эти коды преобразуются в каждом вычислителе 26 так же, как это происходит в вычислителях 12. После поступления n-го элемента кодового слова на вход второго кольцевого счетчика 25 на его выходе переполнения появляется импульс, который, обнуляя третий блок оперативной памяти 29, переносит информацию с его выходов в ячейки памяти четвертого блока оперативной памяти 37 и с выходов второй группы вычислителей 26 - на входы блока принятия решения 30, блока принятия решения 31 и вычислителя 32. Если ошибки в принятом сообщении отсутствуют, с выхода блока принятия решения 30 на управляющий вход третьего ключа 38 поступает команда, открывающая его. Импульсы с выхода генератора 23 с частотой повторения, в k/n раз меньшей частоты повторения элементов кодового слова, поступают на информационный вход второго ключа 27, который, будучи изначально в запертом состоянии, не пропускает их на вход второго кольцевого счетчика 39. Эти же импульсы приходят на вход второго удвоителя 24, увеличивающего в 2 раза частоту повторения поступающих импульсов, и с его выхода - на вход второго кольцевого счетчика 28. С приходом [2(k+1)+1] -гo импульса (приблизительно посередине промежутка времени между моментами прихода на вход декодера 6 последнего элемента текущего и первого элемента следующего за ним кодового слова) на вход кольцевого счетчика 28 с его выхода переполнения поступает импульс на счетный вход второго триггера 36, опрокидывая его. Образовавшееся на выходе второго триггера 36 напряжение "логической единицы" передается на прямой вход второго элемента И 33. Поскольку второй кольцевой счетчик 39 еще не начал счет, на его выходе переполнения будет сохраняться напряжение "логического нуля" и, следовательно, на выходе второго элемента И 33 появится напряжение "логической единицы", открывающее второй ключ 27. Импульсы с выхода генератора 23 станут поступать на вход второго кольцевого счетчика 39, в результате чего на его информационном выходе появится код, сменяющийся с каждым вновь подсчитанным импульсом. Этот код пройдет через уже открытый третий ключ 38 и, попав на адресный вход четвертого блока оперативной памяти 37, будет инициировать сброс информации из его ячейки, имеющей тот же порядковый номер, что и импульс, подсчитанный вторым кольцевым счетчиком 39, и k информационных элементов кодового слова будут последовательно переданы на выход неисправляемого сообщения декодера. Проверочные же элементы останутся за ненадобностью в ячейках памяти четвертого блока оперативной памяти 37 и будут замещены в ней проверочными элементами следующего кодового слова. После поступления k-го импульса на вход второго кольцевого счетчика 39 на его выходе переполнения появится напряжение "логической единицы", которое сбросит первый триггер 36, и на выходе второго элемента И 33 появится напряжение "логического нуля", закрывающее второй ключ 27 и прекращающее поступление импульсов с выхода генератора 23 на вход второго кольцевого счетчика 39, подготавливая его к следующему циклу работы.

Если в принятом сообщении обнаружена одна ошибка, с выхода блока принятия решения 31 на управляющий вход третьего ключа 38 поступает команда, открывающая его и запускающая вычислитель 32. Вычислитель 32 определяет величину ошибки и ее порядковый номер в принятом сообщении и при появлении на его тактовом входе импульса с информационного выхода второго кольцевого счетчика 39 направляет сигнал ошибки на вход вычислителя 35. В вычислителе 35 сигнал ошибки преобразуется по правилу g² и суммируется в сумматоре 40 с соответствующим элементом принятого сообщения, поступившим с выхода четвертого блока памяти 37, по правилу суммирования элементов абелевой группы, исправляя ошибку и пропуская на выход исправляемого сообщения декодера скорректированное сообщение.

Блок принятия решения 30, блок принятия решения 31 и вычислитель 32 могут быть реализованы программным путем на алгоритмическом языке, например QBASIC, с использованием типового микропроцессора.

Программа для реализации блока принятия решения 30.

Значения m элементов синдрома s с выходов второй группы из m вычислителей 26 поступают в область памяти с именем DATA.

DATA s1, s2 . . . sm

Исходное состояние ячеек памяти:

erdecod$ = "декодировать"

msg$ = " "

e = 0 "код значения единичного элемента

none = e "начальное значение неединичного элемента

countnone = 0 "счетчик числа неединичных элементов

m= 3: k= 4: n= k+m "параметры проверочной матрицы

pozer = n + 1 "начальное значение указателя позиции ошибки

Формирование в оперативной памяти области для массива s

DIM s(m)

Формирование в оперативной памяти области для массива проверочной матрицы h$

DIM h$(m, n)

В области памяти DATA находятся значения элементов проверочной матрицы

DATA+e, +e, +e, -x, +e, +e, +e, -x, +e, +e, +e, -x

DATA +е, -х, -х, -х, +е, -х, -х, -х, +е

Загрузка в оперативную память m значений элементов синдрома

FOR i - 1 TO m: READ s(i): NEXT i

Загрузка в оперативную память проверочной матрицы

FORj = 1 ТО n: FOR i = 1 ТО m: READ h$(i, j): NEXTi: NEXTj

Подсчет количества неединичных элементов в синдроме и, если их количество равно нулю, принятие решения о декодировании принятого сообщения

с - 0: FOR i = 1 ТО m: IF s(i) <> e THEN с = c+1 NEXT i: countnone = с

IF countnone = 0 THEN msg$ = erdecod$

END

Программа для реализации блока принятия решения 31.

Значения m элементов синдрома s с выходов второй группы из m вычислителей 26 поступают в область памяти с именем DATA, в которой уже хранится значение числа m.

DAТA s1, s2 . . . sm

Исходное состояние ячеек памяти:

erdecod$ = "декодировать"

msg$ -= " "

е = 0 "код значения единичного элемента

none = e "начальное значение неединичного элемента

countnone = 0 "счетчик числа неединичных элементов

m= 3: k= 4: n= k+m "параметры проверочной матрицы

pozer = n+1 "начальное значение указателя позиции ошибки

Формирование в оперативной памяти области для массива s

DIM s(m)

Формирование в оперативной памяти области для массива проверочной матрицы h$

DIM hS(m, n)

В области памяти DATA находятся значения элементов проверочной матрицы

DATA +е, +е, +е, -х, +е, +е, +е, -х, +е, +е, +е, -х

DATA +е, -х, -х, -х, +е, -х, -х, -х, +е

Загрузка в оперативную память m значений элементов синдрома

FOR i = 1 TO m: READ s(i): NEXT i

Загрузка в оперативную память проверочной матрицы

FORj = 1 ТО n: FOR i = 1 TO m: READ h$(i, j): NEXT i: NEXTj

Подсчет количества неединичных элементов в синдроме и, если их количество равно единице, принятие решения о декодировании принятого сообщения

с = 0: FOR i = 1 ТО m: IF s(i) <> e THEN с = c+1 NEXT i: countnone = с

IF countnone = 1 THEN msg$ = erdecod$

END

Программа для реализации вычислителя 32.

Значения m элементов синдрома s с выходов второй группы из m вычислителей 26 поступают в область памяти с именем DATA.

DATA s1, s2 . . . sm

Исходное состояние ячеек памяти:

erdecod$ = "декодировать"

msg$ = " "

e = 0 "код значения единичного элемента

none = е "начальное значение неединичного элемента

countnone = 0 "счетчик числа неединичных элементов

m= 3: k= 4: n= k+m "параметры проверочной матрицы

pozer = n + 1 "начальное значение указателя позиции ошибки

Формирование в оперативной памяти области для массива s

DIM s(m)

Формирование в оперативной памяти области для массива проверочной матрицы h$

DIM h$(m, n)

В области памяти DATA находятся значения элементов проверочной матрицы

DATA +е, +е, +е, -х, +е, +е, +е, -х, +е, +е, +е, -х

DATA +е, -х, -х, -х, +е, -х, -х, -х, +е

Загрузка в оперативную память m значений элементов синдрома

FOR i = 1 TO m: READ s(i): NEXT i

Загрузка в оперативную память проверочной матрицы

FORj = 1 ТО n: FOR i = 1 TO m: READ h$(i, j): NEXT i: NEXTj

Вычисление первого неединичного элемента в синдроме

FOR i = 1 ТО m

IF s(i)= e THEN GOTO nxi:

none = s(i)

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

FOR j = i+1 TO m

IF s(i) = e THEN GOTO nxj

IF s(j) = none THEN GOTO nxj

GOTO moutl

nxj: NEXTj

nxi: NEXTi

Вычисление pozer - номера позиции ошибки в принятом сообщении

FORj = 1TOk

pozer = j

FOR i - 1TOm

IF s(i) - none AND h$(i, j) = "+e" OR s(i) = e AND h$(i, j) = "-x" THEN p = 1

ELSE p - 0

END IF

IF p= 0 THEN GOTO nj

NEXT i

IF p = 1 THEN GOTO moutl

nj: NEXTj

Занесение значения ошибки в ячейку памяти с именем none и ее номера в принятом сообщении в ячейку с именем pozer

mout1:

END

ЛИТЕРАТУРА.

1. Дж. Кларк, мл. , Дж. Кейн. Кодирование с исправлением ошибок в системах цифровой связи. Перевод с английского С. И. Гельфанда. /Под редакцией Б. С. Цыбакова. Выпуск 28. - М. - Радио и связь, 1987, с. с. 9-18, рис. 1.2.

2. А. И. Кострикин. Введение в алгебру. - М. : Наука, 1977.