Матричное вычислительное устройство Советский патент 1993 года по МПК G06F15/31 

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

Цель изобретения - упрощение устройства.

На фиг.1 приведена схема матричного вычислительного устройства; на фиг.2 - схема вычислительной ячейки матрицы.

Матричное вычислительное устройство содержит вычислительные ячейки 1, инверторы 2, сумматоры 3, входы 9, выходы 10, выходы 11.

Каждая вычислительная ячейка содержит триггер 4, элемент И 5, два двоичных сумматора 6 и 7, элемент ИЛИ 8, первый и

второй установочные входы 12 и 13 вычислительных ячеек.

Устройство работает следующим образом.

Устройство может осуществлять кодирование или декодирование. При этом оно работает в двух режимах: настройки и рабочем.

При кодировании в режиме настройки, в триггеры 4, которые могут быть RS или D триггерами, каждый вычислительной ячейки 1 матрицы записываются элементы порождающей матрицы кода С. Для (n, k) кода, в котором количество кодовых символов равно п, а количество информационных символов равно k, порождающая матрица кода содержит k строк и п столбцов. Для (n, k)

со

00 00 00

о

кода, представленного в систематическом виде, когда информационные сигналы помещаются в старшие разряды, а провероч- ные символы в младшие разряды, и порождающая матрица кода G состоит из единичной подматрицы 1 и подматрицы проверочных символов Р/С 1 : Р, в триггеры каждой вычислительной ячейки матрицы записываются подматрицы проверочных символов Р, которая содержит к строк и n-k столбцов.

В рабочем режиме на входы 9 устройства подается информационное слово а(х). Каждый разряд информационного слова поступает на первые входы вычислительных ячеек соответствующей строки матрицы. В каждой вычислительной ячейке на выходе элемента И 5 формируется результат конъюнкции разряда информационного слова и значений элементов матрицы кода, записанных в триггеры вычислительных ячеек соответствующей строки матрицы. Результат конъюнкции поступает на первый вход двоичного сумматора, на второй вход которого, совпадающего со вторым входом вычислительной ячейки, поступает результат двоичного сложения предыдущей строки матрицы, а выход двоичного сумматора, совпадающий с первым выходом вычислительной ячейки, поступает на второй вход двоичного сумматора последующей строки матрицы. На вторые входы вычислительных ячеек первой строки матрицы поступают сигналы значения О, а первые выходы вычислительных ячеек последней строки матрицы поступают на выходы 10 устройства и являются кодовыми символами с(х) или проверочными символами э(х) при систематическом представлении кода. Таким образом, при кодировании в общем случае получается результат умножения информационного слова на порождающую матрицу кода, в результате чего образуется кодовое слово:

I

c(x) o(x).G.

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

р(х) 3(

кодовое слово получается подстановкой информационных символов в старшие разряды, а проверочных символов в младшие разряды кодового слова:

(х)

0(x).xn-k +

(х)

При кодировании значение выходов 11 устройства несущественно.

При декодировании, в режиме настройки, в триггеры 4 каждой вычислительной

ячейки 1 матрицы записываются элементы транспонированной проверочной матрицы кода Нт. Для (п, К) кода, независимо от формы представления кода, транспонированная матрица кода содержит п строк и n-k

столбцов.

В рабочем режиме на входы 9 устройства подается принятое кодовое слово v(x). Каждый разряд принятого кодового слова поступает на первые входы вычислительных

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

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

совпадающий с первым выходом вычислительной ячейки, поступает на двшчный сумматор последующей строки матрицы. На вторые входы вычислительных ячеек пер- вой строки матрицы поступают сигналы значения О, а первые выходы вычислительных ячеек последней строки матрицы поступают на выходы 10 устройства соответствующего столбца матрицы и являются символами синдрома ошибок 5(х). Таким образом, на

первом этапе декодирования получается результат умножения принятого кодового слова на транспортированную проверочную матрицу кода, в результате чего образуется синдром ошибок:

3(х) Г(х).Нт

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

входом вычислительной ячейки поступает результат дезъюнкции предыдущего столбца матрицы, а выход элемента ИЛИ, совпадающего со вторым выходом вычислительной ячейки, поступает на эле- мент ИЛИ последующего столбца матрицы. На четвертые входы вычислительных ячеек первого столбца матрицы поступают сигналы значения О, а вторые выходы вычислительных ячеек последнего столбца матрицы поступает на входы инверторов 2 соответствующей строки матрицы и являются символами вектора ошибок е(х). Таким образом, на втором этапе декодирования получается результат сравнения синдрома ошибок и каждой строки матрицы, в результате чего образуется вектор ошибок, который представляет собой слово с единицами в тех разрядах, где синдром ошибок равен строке матрицы, что соответствует ошибке в соответствующем разряде принятого кодового слова.

Вектор ошибок е(х) с выходов инвертора 2 поступает на вторые входы двоичных сумматоров 3, на первые входы которых по- ступают соответствующие разряды принятого кодового слова. Таким образом, на третьем этапе декодирования принятое кодовое слово складывается по модулю два с вектором ошибок и на выходах 11 устройства получается исправленное кодовое слово:

(х) (х) + е(х)

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

5 10 15 0

5 0

5

0 5 0 5

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

j 11

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

ю

10Ю

Фи2.1