STEM Problem Detail

Problem #75

Design and Technology Hard

Problem Statement

Prompt

Provide me the solution of Question 9.6.

Solution Rendering...

## 8-bit LFSR Implementation using 16V8 PLD

This document presents an 8-bit Linear Feedback Shift Register (LFSR) implementation using a single 16V8 PLD. The LFSR generates a pseudo-random bit stream suitable for the SEN input in the modified guessing game from Exercise 9.5. The analysis includes periodicity calculations and maximum run lengths of consecutive 0s and 1s.

## Design Requirements

- Implement 8-bit LFSR using one 16V8 PLD
- Generate pseudo-random bit stream from one output
- Analyze: Period (when sequence repeats)
- Analyze: Maximum consecutive 0s and 1s

---

## LFSR Theory

### Maximal-Length LFSR

For an 8-bit LFSR, maximal length sequence $= 2^8 - 1 = 255$ states (excluding all-zeros).

### Feedback Polynomial Selection

Common 8-bit maximal-length polynomial: $x^8 + x^6 + x^5 + x^4 + 1$

| **Polynomial** | **Sequence Length** |
|---|---|
| $x^8 + x^6 + x^5 + x^4 + 1$ | 255 |
| $x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1$ | 255 |
| $x^8 + x^7 + x^2 + x + 1$ | 255 |

We'll use: $x^8 + x^6 + x^5 + x^4 + 1$

---

## 16V8 PLD Architecture

**Pin assignments for the 16V8:**

| Side | Pin | Signal |
|---|---|---|
| Input | 1 | CLK |
| Input | 2 | RESET |
| Input | 3–9 | NC (not connected) |
| Output | 19 | Q7 (MSB) |
| Output | 18 | Q6 |
| Output | 17 | Q5 |
| Output | 16 | Q4 |
| Output | 15 | Q3 |
| Output | 14 | Q2 |
| Output | 13 | Q1 |
| Output | 12 | Q0 (LSB) |

Feedback path: Q7 (pin 19) feeds back into the XOR network to produce the new Q0 input on the next clock cycle.

---

## ABEL Implementation

```abel
MODULE lfsr_8bit
TITLE '8-bit Linear Feedback Shift Register for 16V8'

" 16V8 Pin Assignments
" Pins 1-9: Inputs, Pins 12-19: Outputs

" Input Declarations
CLK PIN 1; " Clock input
RESET PIN 2; " Active-high reset
NC3 PIN 3; " Not connected
NC4 PIN 4; " Not connected
NC5 PIN 5; " Not connected
NC6 PIN 6; " Not connected
NC7 PIN 7; " Not connected
NC8 PIN 8; " Not connected
NC9 PIN 9; " Not connected

" Output Declarations (registered outputs)
Q0 PIN 12 ISTYPE 'reg'; " LSB
Q1 PIN 13 ISTYPE 'reg';
Q2 PIN 14 ISTYPE 'reg';
Q3 PIN 15 ISTYPE 'reg';
Q4 PIN 16 ISTYPE 'reg';
Q5 PIN 17 ISTYPE 'reg';
Q6 PIN 18 ISTYPE 'reg';
Q7 PIN 19 ISTYPE 'reg'; " MSB - use as SEN output

" LFSR Feedback Polynomial: x^8 + x^6 + x^5 + x^4 + 1
" Feedback = Q7 xor Q5 xor Q4 xor Q3

EQUATIONS

FEEDBACK = Q7 $ Q5 $ Q4 $ Q3; " XOR operations

Q7 := Q6;
Q6 := Q5;
Q5 := Q4;
Q4 := Q3;
Q3 := Q2;
Q2 := Q1;
Q1 := Q0;
Q0 := FEEDBACK;

" Reset initialization (non-zero seed)
WHEN (RESET) THEN
Q7 := 1; Q6 := 0; Q5 := 0; Q4 := 0;
Q3 := 0; Q2 := 0; Q1 := 0; Q0 := 1;
ENDWITH;

TEST_VECTORS
([CLK, RESET] -> [Q7, Q6, Q5, Q4, Q3, Q2, Q1, Q0])

[.C., 1] -> [1, 0, 0, 0, 0, 0, 0, 1]; " Initial state: 10000001
[.C., 0] -> [0, 0, 0, 0, 0, 0, 1, ?];
[.C., 0] -> [0, 0, 0, 0, 0, 1, ?, ?];
[.C., 0] -> [0, 0, 0, 0, 1, ?, ?, ?];
[.C., 0] -> [0, 0, 0, 1, ?, ?, ?, ?];

END lfsr_8bit;
```

---

## Alternative Implementation with Different Polynomial

```abel
MODULE lfsr_8bit_alt
TITLE '8-bit LFSR with polynomial x^8 + x^7 + x^2 + x + 1'

CLK, RESET PIN;
Q7..Q0 PIN ISTYPE 'reg';

" Polynomial: x^8 + x^7 + x^2 + x + 1
" Feedback = Q7 xor Q6 xor Q1 xor Q0
EQUATIONS
FEEDBACK = Q7 $ Q6 $ Q1 $ Q0;

Q7 := Q6;
Q6 := Q5;
Q5 := Q4;
Q4 := Q3;
Q3 := Q2;
Q2 := Q1;
Q1 := Q0;
Q0 := FEEDBACK;

WHEN (RESET) THEN
Q7 := 1; Q6 := 0; Q5 := 1; Q4 := 0;
Q3 := 1; Q2 := 1; Q1 := 1; Q0 := 0;
ENDWITH;

END lfsr_8bit_alt;
```

---

## Periodicity Analysis

### Sequence Length

$$\text{Period} = 2^8 - 1 = 255\ \text{clock cycles}$$

### All-Zeros State Handling

The all-zeros state (00000000) is not part of the maximal sequence. If entered:

$$\text{Feedback} = 0 \oplus 0 \oplus 0 \oplus 0 = 0$$

The register stays at all-zeros forever. Solutions:

1. Initialize to non-zero seed (done in ABEL above)
2. Add logic to detect all-zeros and jump to non-zero:

```abel
" Add to EQUATIONS section:
WHEN ([Q7,Q6,Q5,Q4,Q3,Q2,Q1,Q0] == [0,0,0,0,0,0,0,0]) THEN
Q0 := 1;
ENDWITH;
```

---

## Run Length Analysis

### Theoretical Maximum Run Lengths

For a maximal-length LFSR of length $n$:

- Maximum consecutive 1s: $n$ (all-ones state)
- Maximum consecutive 0s: $n - 1$ (all-zeros excluded)

For 8-bit LFSR:

$$\text{Max consecutive 1s} = 8, \qquad \text{Max consecutive 0s} = 7$$

### Empirical Verification

The feedback function for $x^8 + x^6 + x^5 + x^4 + 1$ is:

$$f = Q_7 \oplus Q_5 \oplus Q_4 \oplus Q_3$$

The all-ones state (11111111) produces:

$$f = 1 \oplus 1 \oplus 1 \oplus 1 = 0$$

Next state: 11111110 (seven 1s followed by 0). Thus the maximum run of 1s is actually **7**, not 8.

### Run Length Distribution

| **Run Length** | **Number of 0 Runs** | **Number of 1 Runs** |
|---|---|---|
| 1 | 64 | 64 |
| 2 | 32 | 32 |
| 3 | 16 | 16 |
| 4 | 8 | 8 |
| 5 | 4 | 4 |
| 6 | 2 | 2 |
| 7 | 1 | 1 |
| 8 | 0 | 0 |

---

## 16V8 Resource Analysis

| **Resource** | **Used** | **Available** | **Utilization** |
|---|---|---|---|
| Input Pins | 2 (CLK, RESET) | 10 | 20% |
| Output Pins | 8 (Q7–Q0) | 8 | 100% |
| Flip-Flops | 8 | 8 | 100% |
| AND Terms per Output | 2–4 | 8 | 25–50% |
| Total AND Terms | ~24 | 64 | 37.5% |
| **Fits in 16V8?** | **Yes** | | |

### Product Term Analysis

\begin{align*}
Q7_{\text{next}} &= Q6 \quad \text{(1 term)} \\
Q6_{\text{next}} &= Q5 \quad \text{(1 term)} \\
Q5_{\text{next}} &= Q4 \quad \text{(1 term)} \\
Q4_{\text{next}} &= Q3 \quad \text{(1 term)} \\
Q3_{\text{next}} &= Q2 \quad \text{(1 term)} \\
Q2_{\text{next}} &= Q1 \quad \text{(1 term)} \\
Q1_{\text{next}} &= Q0 \quad \text{(1 term)} \\
Q0_{\text{next}} &= Q7 \oplus Q5 \oplus Q4 \oplus Q3 \quad \text{(4 terms)}
\end{align*}

Maximum product terms per output: 4 (well under the 8-term limit).

---

## Implementation for SEN Generation

### Complete System Integration

**Block diagram:**

```
+-------------+ SEN (Q7) +--------------+
CLK --->| 8-bit LFSR |---------------------->| Guessing Game|
| 16V8 | | 16V8 |
RESET-->| | | |
+-------------+ +--------------+
^ ^
| |
CLK -----------------------------------CLK
RESET

Period = 255 cycles | Max 0s = 7 | Max 1s = 7
```

### Synchronization Considerations

- LFSR and game use the same CLK for synchronization
- RESET initializes both to known states
- SEN changes on the rising clock edge
- Game samples SEN synchronously

---

## Testing and Verification

```abel
MODULE lfsr_test
TITLE 'Test bench for 8-bit LFSR'

lfsr_8bit device;

TEST_SEQUENCE

" 1. Verify period is 255
REPEAT 256;
@CYCLE CLK;
IF (COUNT == 255) THEN
ASSERT (device.Q == 8'b10000001);
ENDIF;
ENDREPEAT;

" 2. Verify maximum run lengths
RUN_LENGTH_TEST:
MAX_ONES = 0;
CURRENT_ONES = 0;
REPEAT 1000;
@CYCLE CLK;
IF (device.Q7 == 1) THEN
CURRENT_ONES = CURRENT_ONES + 1;
IF (CURRENT_ONES > MAX_ONES) THEN
MAX_ONES = CURRENT_ONES;
ENDIF;
ELSE
CURRENT_ONES = 0;
ENDIF;
ENDREPEAT;
ASSERT (MAX_ONES <= 7);

" 3. Verify no all-zeros state
REPEAT 1000;
@CYCLE CLK;
ASSERT (device.Q != 8'b00000000);
ENDREPEAT;

END lfsr_test;
```

---

## Conclusion

1. **Implementation successful:** 8-bit LFSR fits in a single 16V8
- Uses 2 inputs, 8 registered outputs
- Maximum 4 product terms per output (well under 8 limit)
- Total resource utilization: ~37.5%

2. **Periodicity:** Sequence repeats every 255 clock cycles
- $2^8 - 1 = 255$ states (maximal length)
- All-zeros state excluded (handled by initialization)

3. **Run lengths:**
- **Maximum consecutive 0s:** 7
- **Maximum consecutive 1s:** 7
- For polynomial $x^8 + x^6 + x^5 + x^4 + 1$

4. **Suitability for game:** Provides good pseudo-randomness
- Unpredictable state advancement timing
- Long period (255) before repetition
- Balanced run lengths (max 7)

5. **Alternative:** Different polynomials available if different run length properties are needed.

The 8-bit LFSR implementation successfully meets all requirements and provides a suitable pseudo-random bit stream for enhancing the guessing game's unpredictability while fitting comfortably within a 16V8 PLD.

Loading solution...

← Previous Problem

Back to List

Next Problem →