Electronic – Polynomial division LFSR

digital-logic

Here is the schematic for LFSR (Linear Feedback Shift Register) polynomial division by \$w(x) = n_3x^3 + n_2x^2 + n_1x + n_0\$

enter image description here

\$\oplus\$ denotes adder without carry logic, (nx) denotes multiplicator by \$n_x\$ coefficient and boxes are flip-flops.

The drawback of this solution is that polynomial \$w(x)\$ has to be of constant degree, otherwise the circuit won't work.

Are there are any solutions to build LFSR division unit which is able to divide by polynomial of non-constant-degree (there is specified maximally allowed degree)? Or maybe some not-LFSR units?

Best Answer

I think what you want is to have a multiplexer between the IN bit and the LFSR which will route the input bit around unneeded LFSR stages. This would require lines to not only deactivate unused stages but to reroute the output bit from one stage to another. It's possible but is going to be fairly hardware expensive. What is the purpose of having a variable-degree LFSR in hardware?

Related Solutions

Electronic – hardware implementation of division algorithm

Flowcharts are often not a very precise way of indicating what hardware is doing, since flowcharts often imply the existence of a single execution process, whereas hardware often does many overlapping and simultaneous operations.

The portions of the diagram circled in red seem a bit odd. It seems odd to latch A with the value after subtracting B, and then re-add B. More natural would simply be to not bother latching the lower part of the subtraction result. I think the flowchart might be clearer if "named values" were separated into "registers" and "values", and each step either computed values or registers. Thus, for example, one could have something like (assuming 16-bit registers)

C:T[15..0] = (A[14..0]:Q[15]) + ~B-1
if (C or A[15])
  A[15..0] = (A[14..0]:Q[15])
  Q[15..1] = Q[14..0]
  Q[0] = 1
Else
  A[15..0] = T[15..0]
  Q[15..1] = Q[14..0]
  Q[0] = 0
Endif

Every step that updates registers would represent a system clock. Events that merely compute values would not require a clock edge, but would be processed asynchronously.

Using a Counter to Determine next MSB position in polynomial division

I assume that ctr_reg is of type (un)signed because it's a counter.

VHDL expect normal indices to be of type integer (natural, positive are subtypes of integer). See the definition for std_logic_vector:

type STD_LOGIC_VECTOR is array (NATURAL range <>) of STD_LOGIC;

So you must convert your counter from (un)signed to integer:

if (numerator(to_integer(ctr_reg)) = '1') then

If ctr_reg is of type std_logic_vector (slv), then you must also convert slv to unsigned:

if (numerator(to_integer(unsigned(ctr_reg))) = '1') then

If this construct is to long, write a function (let's say to_index(..)) which hides these conversions :)

if (numerator(to_index(ctr_reg)) = '1') then

A definition for to_index(..) can be found here.

Edit 1:

List of commonly used packages in VHDL:

library IEEE;
use     IEEE.STD_LOGIC_1164.ALL;  -- common std_logic(_vector) operations
use     IEEE.NUMERIC_STD.ALL;     -- defines signed and unsigned and their operations

Best Answer

Related Solutions

Electronic – hardware implementation of division algorithm

Using a Counter to Determine next MSB position in polynomial division

Related Topic