# US 2015/0160922 A1 · N-Valued Shift Registers with Inverter Reduced Feedback Logic Functions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0160922 A1
- Document ID: US20150160922A1
- Status: Published application
- Kind: A1
- Application number: 14/622,860
- Filed: 2015-02-14
- Published: 2015-06-11
- Earliest claimed: 2003-09-09
- Assignees: Ternarylogic LLC
- Inventors: Peter Lablans
- Web page: https://patentgrep.com/patent/US20150160922A1

## CPC

- G06F 7/4876: {Multiplying}
- G06F 5/012: {in floating-point computations}
- H03M 7/00: Conversion of a code where information is represented by a given sequence or number of digits to a code where the same {, similar or subset of} information is represented by a different sequence or number of digits
- H03M 13/158: {Finite field arithmetic processing}
- H04L 9/06: the encryption apparatus using shift registers or memories for block-wise {or stream} coding, e.g. DES systems {or RC4; Hash functions; Pseudorandom sequence generators}
- H03M 13/09: Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/19: Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
- H03M 13/23: using convolutional codes, e.g. unit memory codes
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Methods and apparatus reducing the number of multipliers in Galois Field arithmetic are disclosed. Methods and apparatus for implementing n-valued Linear Feedback Shift Register (LFSR) based applications with a reduced number of multipliers are also disclosed. N-valued LFSRs with reduced numbers of multipliers in Fibonacci and in Galois configuration are demonstrated. Multiplier reduction methods are extended to n-valued functions with more than 2 inputs. Methods to create multiplier reduced multi-input n-valued function truth tables are disclosed. Methods and apparatus to implement these truth tables with a limited number of n-valued inverters are also disclosed. Scrambler/descrambler combinations with adders and multipliers over GF(2p) are provided. Communication, data storage and digital rights management systems using multiplier reduction methods and apparatus or the disclosed scrambler/descrambler combination are also provided.

## Claims

### Claim 1

A device to generate n-valued symbols, each n-valued symbol having one of n values with n=2p and p>1 and being represented by a signal, comprising:
an n-valued shift register with feedback, including a plurality of shift register elements and an implementation of an n-valued logic function;
a memory having a first input and a second input, the memory storing a single non-commutative n-valued truth table implementing the n-valued logic function, which is an addition over an n-valued finite field that is modified by an n-valued inverter, the memory being part of the n-valued shift register with feedback, wherein the first input and the second input each are enabled to receive an n-valued symbol provided by a shift register element of the n-valued shift register that determine a symbol in the single non-commutative n-valued truth table as an output symbol of the n-valued logic function;
an output of the device to provide an n-valued symbol, wherein the device is selected from the group consisting of: scrambler, descrambler, sequence generator, generator of symbols of an error correction code, and a Cyclic Redundancy Check (CRC) coder.

### Claim 2 (depends on 1)

The device of claim 1, wherein the error correction code is at least one of a Reed Solomon code or a convolutional code.

### Claim 3 (depends on 1)

The device of claim 1, wherein the n-valued inverter is a multiplier over the n-valued finite field.

### Claim 4 (depends on 1)

The device of claim 1, wherein the n-valued inverter is not a multiplier over the n-valued finite field.

### Claim 5 (depends on 1)

The device of claim 1, wherein an n-valued symbol is represented by a plurality of binary symbols.

### Claim 6 (depends on 1)

The device of claim 1, wherein the shift register with feedback is a Linear Feedback Shift Register (LFSR).

### Claim 7 (depends on 6)

The device of claim 6, wherein the LFSR performs a polynomial multiplication.

### Claim 8 (depends on 6)

The device of claim 6, wherein the LFSR performs a polynomial division.

### Claim 9 (depends on 1)

The device of claim 1, wherein the device is part of a communication system or a data storage system.

### Claim 10 (depends on 1)

The device of claim 1, wherein the device is part of a digital rights management system.

### Claim 11

An n-valued shift register with feedback to process n-valued symbols with n>2, wherein each n-valued symbol is represented by one or more signals, comprising:
a plurality of n-valued shift register elements;
a memory device that stores a single n-valued non-commutative truth table that is determined by modifying an n-valued commutative truth table with an n-valued inverter, the single n-valued non-commutative truth implementing an n-valued feedback logic function in the n-valued shift register with feedback and outputting an n-valued symbol in accordance with the single n-valued non-commutative truth table based on n-valued symbols from two n-valued shift register elements in the plurality of shift register elements; and
an output of the n-valued shift register with feedback to provide an n-valued symbol, wherein the n-valued shift register with feedback is part of the group consisting of: scrambler, sequence generator, generator of symbols of a code, and a Cyclic Redundancy Check (CRC) coder.

### Claim 12 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the n-valued commutative truth table is an addition over an n-valued finite field.

### Claim 13 (depends on 12)

The n-valued shift register with feedback of claim 12, wherein n=2p with p>1.

### Claim 14 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the code is a convolutional code.

### Claim 15 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the n-valued inverter is a multiplier over the n-valued finite field.

### Claim 16 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the n-valued inverter is not a multiplier over the n-valued finite field.

### Claim 17 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein an n-valued symbol is represented by a plurality of binary symbols.

### Claim 18 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the n-valued shift register with feedback is a Linear Feedback Shift Register (LFSR).

### Claim 19 (depends on 18)

The n-valued shift register with feedback of claim 18, wherein the LFSR performs at least one of a polynomial multiplication and a polynomial division.

### Claim 20 (depends on 11)

The n-valued shift register with feedback of claim 11, wherein the n-valued shift register with feedback is part of the group consisting of a data storage system and a communication system.
