SU1709302A1 - Device for performing operations on finite field members - Google Patents

Abstract

The invention relates to computing technique and can be used in encoding and decoding devices of binary codes whose check matrices contain elements of finite fields GF.

Description

The invention relates to computing and can be used in binary coding and decoding devices whose check matrices contain elements of finite fields (GFCa).

The purpose of the invention is to expand the functionality by performing a division operation.

FIG. 1 shows a diagram of the device; in fig. 2 is a multiplication module diagram.

The device (Fig. 1) contains the first 1, made in the form of a register, and the second 2, made in the form of a counter, memory buffer nodes, multiplication module 3, the HE element 4, the first 5 and the second 6 elements AND LINE, the memory element 7 , the first 8 and second 9 elements And, the output 10 of the uncertainty of the result of the device, the clock input 11 of the device, the input 12 of the operation code of the device, the output 13 of the resolution of recording the dividend polynomial.

Module 3 multiplication (Fig.2} contains tons of elements AND 14, t-1 of blocks 15 of matrix transformation and m multi-input adders 16.

The indices for the numbers of elements, inputs and outputs of the elements and units of the device, varying from 1 to m inclusive, determine their correspondence to coefficients for those powers of the fictitious variable in the polynomials-operands whose values are one less than the values of the indices.

The device works as follows.

In the initial state (Fig. 1), the buffer nodes 1 and 2 of the memory and the memory element 7 are reset.

A series of clock pulses is applied to the device input 11, and to all other device inputs, the signals O, respectively. At the same time, at the output of the memory element 7, at the outputs of the buffer nodes 1 and 2 of the memory, signals O are generated. the inputs of element 5 OR do NOT receive signals O respectively. Consequently, at the output of element 5 OR-NOT, at the outputs of elements AND 8 and 9, as well as at the outputs of module 3 multiplication, according to the value of input p6 clinomas-multipliers equal to zero (Fig. 2), signals O are generated respectively. At the same time, signal O is received at the input of element 4 (figure 1), and signal 1 is generated at its output. Therefore, signal 1 arrives at the first input of element 6 OR-NOT. Therefore, at its output, which means.

At output 13 of the device and at the input of the installation in memory element 7, signal O is generated.

Since the inputs of the elements And 8 and 9

O signals arrive at their outputs, and therefore, at the output 10 of the device and at the second (secondary) input of the buffer node 2 of the memory, signals O are generated, respectively. This means that the signals at the outputs of the buffer node 2 of the memory do not change.

When the device performs the operation of multiplying two polynomials over the final field GF (), the information inputs of the buffer nodes 1 and 2 of the memory are given the signals corresponding to the coefficients of the first and second three polynomials of factors, respectively.

This means that at the outputs of the buffer nodes 1 and 2, the memory is formed and fed to the inputs

0 of the first and second groups, module 3 multiplication (Fig. 1. 2) signals, corresponding to the coefficients of the first and second polynomial multipliers, respectively.

At the outputs of the module 3 multiplication, which are the outputs of the device, potentials are formed, corresponding to the coefficients of the polynomial-product. The connection of the output of the memory element 7 and the input of the element 8 does not permit the formation of an output

0 element 8 And, and therefore, at output 10, the uncertainty of the result of the device signal 1 when the device performs the operation of multiplying polynomials.

When the device performs an operation

Five divisions of the two polynomials over the end fields GF () in the initial state into the information inputs of the buffer node 1 of the memory 1 are given signals corresponding to the coefficients of the divisor polynomial.

0 At the same time, the inputs of element 5 OR-NOT and the inputs of the first group of module 3 multiplication are given signals corresponding to the coefficients of the polynomial-divider, and the inputs of the second group are signals O, So,

The 5 outputs of the multiplication module 3 generate O signals, i.e. do not change. If the values of all coefficients of the polynomial-divisor are zero, then the output of element 5 is OR NOT, and therefore, the output of element 8

0 And a signal H is formed. In order to start the execution of the division operation, it is necessary to input signal 1 at input 12 of the operation code of the device.

5, the pulse at its clock input will be set to one and its output; hence, at the input of element 9A and at the input of element 8A, a signal 1 is formed.

If the values of all the coefficients of the divisor polynomial are zero, then the output of element 8 I, and therefore the output 10 of the device, a signal 1 is formed, which indicates that the division by zero operation is performed, which in the field of polynomials GF (2) not determined. In this case, the operation of the device is not performed.

If at least one of the coefficients of the poly and ohm-divider is equal to one, then the output of element 5 is OR NOT, and therefore the output 10 of the device through element 8 and the signal O is generated. The output of element 6 OR is NOT the signal O since on. outputs of module 3 multiply by. signals 0 on all inputs of its second group are formed signals O.

This means that at the zero input of the element

7, the signals O are formed at the output 13 of the resolution of the entry of the polynomial-divisible device, and the memory element 7 remains in a single state. In this case, the clock pulses from the clock input 11 of the device to the input element

9 And the signal 1 at its other input, connected to the output of memory element 7, passes to the output of element 9 AND and goes to the second (counting) input of buffer node 2 of memory. In this case, the signals at the outputs of the multiplication module 3 will change and correspond to the polynomial coefficients when multiplying the polynomializer recorded in the buffer memory 1 and the polynomial generated in the buffer memory 2.

The arrival of the clock pulses at the second (counting) input of the buffer node 2 of the memory continues until the signals corresponding to the polynominiunit field GF (), i.e., are generated at the outputs of module 3 multiplication. at the input of the element NOT 4, a signal G will be generated, and at the t-1 inputs of the element 6 OR NOT signals O.

In this case, a signal 1 is formed at the output of the element FILINE. Hence, the output of the resolution of insertion of the multi-functional and the output of the memory element 7 is signaled to 1 and the memory element 7 is set to zero. At the same time, the signal.O. at its output, and therefore, at the input of element 9, and the clock pulses through element 9 AND to the second (counting) input of the buffer node 2 do not pass and, therefore, the state of the buffer node 2 memory

does not change.

According to the Gn signal, the output 13 of the device to the buffer node 1 of the memory, according to its information inputs, the coefficients corresponding to the polynomial are entered, and the signal O is given to the input 12 of the device.

In this case, at the outputs of module 3 multiplications, signals are formed that correspond to the polynomial-partial dividing the polynomial by the divisor polynomial over the final field GF (2).

To perform each of the following operations, it is necessary to first reset the device to its original state and carry out the described operation steps of the device.

Claims (1)

The invention The device for performing operations on elements of finite fields, containing two buffer nodes of the memory, the first of which is made in the form of a register, and a multiplication module consisting of a matrix of mxm elements And (t-bit operands), t-1 blocks matrix transformation and; m multi-input adders, the first and the first inputs of the first memory node are connected to the first and second information inputs of the device, the jth output of the first buffer memory node is connected to the first inputs of m elements AND in each jth column of the multiplication matrix .-. ff column number), the th output of the second buffer node of the memory is connected to the JM input of the first matrix transformation unit of the multiplication module and the second input of the 1, 1) th element of the matrix of the multiplication module (... .... m line number), L output K th block of the matrix transformation which is connected to the 1st input of the (K + 1) th block of the matrix transformation and the second input of the (f, K + 1) th element AND of the matrix of the multiplication module (...., t-1), the outputs (I, j) -x of the elements And the matrix of which is connected to the corresponding inputs m of multi-input adders, the outputs of which are connected to the outputs of the re Ulta device, characterized in that, in order to expand the functionality by performing a division operation, two OR-NOT elements, a NOT element, a memory element and two AND elements are entered into it, and the second buffer memory node is designed as a counter, at the same time out; The first buffer node of the memory is connected to the inputs of the first OR-NOT element, the output of which is connected to the first input of the first element AND, the output of which is connected to the output of the device result uncertainty, the output of enabling the entry of the roll-type of the dividend which is connected to the output of the second element ORINE and the installation input About the memory element, the information input of which is connected to the input of the operation code of the device, the clock input of which is central with the clock input of the memory element and the first input of the second element AND, the second input to the second is connected to the output of the memory element and the second input of the first element I, and the output to the second input of the second buffer memory well, the outputs of the multi-input sums 5 The tori from Ytori by the t-th are connected to (t + 1) inputs of the second OR-NOT element, the t-th input of which is NOT connected to the output of the first multi-input adder via the element. . V "mime 77 / /five, J fS I RU- /five, Isffj j