Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Error correction using finite fields of odd characteristic on binary hardware

a technology of binary hardware and error correction, applied in computing, instruments, coding, etc., can solve the problem of inefficient allocation of 32 bits of register space for operations, and achieve the effect of reducing the need for special modulo-p hardware and speeding up computations

Inactive Publication Date: 2007-06-28
TELEFON AB LM ERICSSON (PUBL)
View PDF4 Cites 21 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Benefits of technology

[0023] Applicants have recognized a need for a computational approach that enables speeding up computations involving basic finite field operations (e.g., addition, multiplication, etc.) for non-binary finite fields even if the available hardware is binary in nature and that reduces need for special modulo-p hardware. In addition, Applicants have recognized a need for a computational approach for non-binary finite fields that utilizes register space more efficiently than conventional methods. For example, it is possible to perform conventional modulo-p arithmetic using a 32-bit CPU, b

Problems solved by technology

For example, it is possible to perform conventional modulo-p arithmetic using a 32-bit CPU, but if p is small (e.g., p=3 or p=7) it is inefficient to devote 32 bits of register space for the operations since the involved quantities (field element coefficients) will only have 2 or 3 significant bits.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Error correction using finite fields of odd characteristic on binary hardware
  • Error correction using finite fields of odd characteristic on binary hardware
  • Error correction using finite fields of odd characteristic on binary hardware

Examples

Experimental program
Comparison scheme
Effect test

example 1

[0107] A numerical example illustrating the approach shown in FIGS. 3 and 4 will now be described with reference to FIG. 5. The operations described below can be carried out using a system such as system 100 shown in FIG. 1, which has been previously described. FIG. 5 illustrates register contents resulting from carrying out the operations as described above with regard to FIGS. 3 and 4. In FIG. 5, reference numerals 501-517 refer to 32-bit registers, and the binary data stored within the registers 501-517 are configured according to a single guard-bit representation. In addition, in this example the binary data represents field elements of the finite field GF(310), and the characteristic p is given by p=2m−1=3. Accordingly, M=2, and 2 bits of register space are allocated for each coefficient of the finite field element. A single guard bit (lightly shaded bit locations) separates adjacent binary data representing adjacent coefficients of the finite field element. In addition, in thi...

example 2

[0196] A numerical example illustrating the approach shown in FIG. 14 for p=2m+1 will now be described with reference to FIG. 15. FIG. 15 schematically illustrates a collection of registers 1501-1521 with exemplary register contents stored therein according to the single-guard-bit representation. Each register 1501-1521 comprises 32 bit locations in this example according to a 32-bit architecture. In this particular example, computations are carried out using binary data representing field elements of GF(56), where p=2m+1=5, and m=2. Accordingly, m+2=4 bits are allocated for each coefficient of the field element (not including guard bits), and adjacent 4-bit groups are separated by a single guard-bit position (lightly shaded regions). In addition, in this example there are two unused bit positions (darkly shaded regions) at the most significant bit positions of each register. The computations described below can be carried out, for example, using a processing system, such as process...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

Binary data representing a code word of an error-correcting code is used for calculating a syndrome, wherein a given portion of the binary data comprises k groups of data bits and represents a field element of the finite field GF(pk), p being an odd prime number, the field element comprising k coefficients in accordance with a polynomial basis representation, each group of data bits of the given portion representing a corresponding one of the k coefficients. The given portion is stored in a first general purpose register and is processed such that the k groups of data bits of the given portion are processed in parallel; determining whether the syndrome is equal to zero; and detecting and correcting errors in the binary data if the syndrome is not equal to zero.

Description

CROSS REFERENCE TO RELATED APPLICATIONS [0001] The present application is related to U.S. patent application entitled “Efficient arithmetic in finite fields of odd characteristic on binary hardware”, Ser. No. ______ (Attorney Docket No. 040000-493), and to U.S. patent application entitled “Cryptography using finite fields of odd characteristic on binary hardware”, Ser. No. ______ (Attorney Docket No. 040001-177), both filed even date herewith, the disclosures of which are incorporated herein by reference in their entirety.BACKGROUND [0002] 1. Field of the Invention [0003] The present invention relates to methods and apparatuses for efficiently carrying out computations in finite fields of odd prime characteristic on binary hardware. The invention is particularly useful for carrying out such computations in cryptography and in error correction, but is not limited to such uses. [0004] 2. Background Information Some Basic Aspects of Finite Fields [0005] A finite field (also called a G...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): H03M13/00
CPCG06F7/724G06F7/725H03M13/158H03M13/6561
Inventor NASLUND, MATSBLOM, ROLF
Owner TELEFON AB LM ERICSSON (PUBL)
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com