Back to results
US 8,898,213 B2Granted
Apparatus and method for division of a Galois field binary polynomial
AssigneesSamsung Electronics Co., Ltd., Kwangwoon University Industry-Academic Collaboration Foundation
InventorsHo Yang, Hyun Seok Lee, Ji Hoon Bang, Young Hwan Park, Ki Taek Bae, Kyeong Yeon Kim
Life of this patent
Estimating the term…
Abstract
An apparatus and method for processing a division of a binary polynomial are provided. The apparatus includes a plurality of exclusive OR (XOR) operators that may perform a selective XOR operation with respect to a conditional bit of a dividend polynomial. The plurality of XOR operators may perform selective XOR operations in parallel and accordingly, a division of a binary polynomial may be rapidly performed.
Claims21
An apparatus, comprising:
- n exclusive OR (XOR) operators to receive a first input value and a second input value, and to generate an output value based on a selective XOR operation value that is obtained by performing a selective XOR operation on the first input value and the second input value, wherein n is an integer equal to or greater than 2;
- a first storage unit to store the first input value;
- and
- a second storage unit to store the second input value,
- wherein, if a Most Significant Bit (MSB) of the second input value is set to “1”, an XOR operation value obtained by performing an XOR operation on the first input value and the second input value is generated as a result of the selective XOR operation,
- wherein, if the MSB of the second input value is set to “0”, the second input value is generated as a result of the selective XOR operation,
- wherein a first input value of each of the n XOR operators is the first binary value,
- wherein a second input value of a first XOR operator from among the n XOR operators is the second binary value, and
- wherein a second input value of a k-th XOR operator among the n XOR operators is obtained by shifting an output of a selective XOR operation value generated by a (k−1)-th XOR operator by one bit to remove a first bit, wherein k is an integer equal to or greater than 2 and equal to or less than n.
6 more elements
A method for dividing a binary polynomial, the method comprising:
- a first load operation of storing, in a dividend storage unit, a value represented by a first portion of a dividend polynomial;
- a first division operation of updating the dividend storage unit with a value that is obtained by shifting a remainder by “q” bits to remove the first “q” bits of the remainder, the remainder being obtained by dividing the value stored in the dividend storage unit by a divisor polynomial;
- a result transfer operation of updating the first division operation value stored in the dividend storage unit with a value obtained by XORing the first division operation value stored in the dividend storage unit and a value represented by a second portion of the dividend polynomial;
- and
- a second division operation of updating the result transfer operation value stored in the dividend storage unit with a value obtained by shifting the result transfer operation value by “q” bits to remove the first “q” bits,
- wherein the first portion and the second portion of the dividend polynomial are consecutive, and “q” represents a difference between a bit length of the dividend storage unit and a bit length of the divisor polynomial.
3 more elements
A non-transitory computer readable storage medium having stored therein program instructions to cause a processor to implement a method comprising:
- a first load operation of storing, in a dividend storage unit, a value represented by a first portion of a dividend polynomial;
- a first division operation of updating the dividend storage unit with a value that is obtained by shifting a remainder by “q” bits to remove the first q bits of the remainder, the remainder being obtained by dividing the value stored in the dividend storage unit by a divisor polynomial;
- a result transfer operation of updating the first division operation value stored in the dividend storage unit with a value obtained by XORing the first division operation value stored in the dividend storage unit and a value represented by a second portion of the dividend polynomial;
- and
- a second division operation of updating the result transfer operation value stored in the dividend storage unit with a value obtained by shifting the result transfer operation value by “q” bits to remove the first “q” bits,
- wherein the first portion and the second portion of the dividend polynomial are consecutive, and “q” represents a difference between a bit length of the dividend storage unit and a bit length of the divisor polynomial.
3 more elements
A single instruction multiple-data (SIMD) processor for performing a division of a binary polynomial, the processor comprising:
- a partitioner configured to partition the binary polynomial into a plurality of portions based on a maximum binary length capable of being processed by an SIMD operator of the SIMD processor;
- and
- an SIMD operator configured to perform a division operation on a first portion of the plurality of portions of the binary polynomial using a divisor polynomial,
- wherein the division operation comprises simultaneously performing selective exclusive OR (XOR) operations on each bit of the first portion from the most significant bit (MSB) to the least significant bit (LSB) using the divisor polynomial.
1 more element
Dependencies are inferred from the claim text.