Patent ID: 9229682
Filing Date: 2016-01-05
CPC Classification: G06F

Claim Text:
1. A parallel device for solving linear equations over finite fields, comprising: an input port, configured to input a coefficient matrix B of linear equations over finite fields, and an irreducible polynomial p(x) selected over a field GF(2 a first processor, comprising a scheduler and a memory interconnected with each other, wherein the scheduler is configured to control a pivot finding component, a partial inversion component, a normalization component and an elimination component, and wherein the memory is configured to store the coefficient matrix B that is inputted and to update the stored coefficient matrix B after each iteration operation; a pivot finding component, comprising a second processor configured to find a pivot β of the coefficient matrix B; a partial inversion component, comprising a third processor configured to implement partial inversion calculation; a normalization component, comprising a fourth processor and m+1 normalization calculation units, wherein the fourth processor is connected to each of the m+1 normalization calculation units to perform scheduling of the m+1 normalization calculation units; an elimination component, comprising a fifth processor and m×(m+1) elimination calculation units, wherein the fifth processor is connected to each of the m×(m+1) elimination calculation units to perform scheduling of the m×(m+1) elimination calculation units and data transmission; and an output port, configured to output solved results of the linear equations over the finite fields, wherein the first processor is connected to the pivot finding component, the partial inversion component, the normalization component, the elimination component, and the input port and the output port, with the partial inversion component being connected to the elimination component and the normalization component, wherein the first processor receives the coefficient matrix B and the irreducible polynomial p(x) selected over the field GF(2 the pivot finding component implements a process of finding the pivot, comprising the steps of: determining whether an element with a row number of g and a column number of g is a none-zero element; if yes, the element is determined to be a pivot, and the pivot finding component sends no back feed into the first processor; if not, then finding none-zero elements one by one among elements with row numbers of g+1 to m and a column number of g; a first none-zero element found is determined to be the pivot β, and the pivot finding component sends the row number of the pivot as feedback to the first processor; the first processor sends the pivot β found to the partial inversion component, and sends the row where the pivot β is in to the normalization component, and sends the other lines of the input coefficient matrix B to the elimination component; the partial inversion component implements partial inversion calculation, and outputs the calculated results to the normalization component and the elimination component; the normalization component and the elimination component implement the normalization calculation and the elimination calculation, and output the calculated results to the first processor; the first processor updates the coefficient matrix B according to the results of the normalization calculation and the elimination calculation, stores the updated coefficient matrix B into the memory, subtracts 1 from the value of the counter, and sets the present counter as j; a next iteration is implemented until the counter reaches 0; if the counter is 0, the last column of the updated coefficient matrix B is outputted into the port as the solved results.