Python Filter Design

I've never really done DSP as part of my day job. I've been to a few training classes and have some texts that just scratch the surface of filter design, modulation, and so on. Never really touched Matlab either. But I've gotten into Python, so I found out there are some interesting modules that handle DSP functions and the related math.

So how hard would it be to come up with a FIR filter that meets certain performance requirements? Well, you can play around with the Python SciPy and NumPy libraries and check the performance of your filter in a few easy lines.

"""
Design a FIR filter and show the frequency response in
a few easy lines
"""

from scipy import signal
from pylab import *

"""
Window types: boxcar, triang, blackman, hamming,
hanning, bartlett, parzen, bohman, blackmanharris,
nuttall, barthann, kaiser (needs beta),
gaussian (needs std),
general_gaussian (needs power, width),
slepian (needs width)
"""

def dbPlot(w, h):
  plot(w, 20 * log(abs(h)) / log(10))

# firwin(number of taps, cutoff relative to Nyquist
# rate, window type)
b = signal.firwin(31, 0.4, window='nuttall')

# freqz(list of zeroes, list of poles)
(w, h) = signal.freqz(b, 1)

plot(w, log(abs(h))/log(10)*20)
show()

This gives me a nice graphic:



You can play around with different windows, as shown in the code comments, or add taps as needed to get the right transition and attenuation.

The Importance of Resets, continued

Checked the Picoblaze support forum. The experts thought that the block RAMs should be settled by the time reset is released. I ran a little experiment with a program that just loads the general purpose with some known values, then writes them to the RAM. Then I ran a loop to configure the FPGA and check the contents of the memory. Once out of a few dozen to a couple hundred times, the first memory location came up wrong.

So it looks like I'll add a reset delay to run at configuration and insure that things are stable before my program starts up. This issue does not seem to have come up anywhere else, so it's kind of a mystery.

Importance of resets

I interrupt the discussion on error correction coding to concentrate on a problem I'm seeing in an ongoing project.

The board comes up, software configures the FPGA, and about one out of two hundred times, the board immediately goes into reset. It appears that the FPGA is asserting a critical tempearture reset, but the board is at room temperature.

The FPGA reads the temperature from a sensor on the board via a SPI bus. So in reproducing the problem and being in this critical temperature state, the SPI signals are captured -- no problem, the temperature from the sensor looks correct. What next?

A Picoblaze microprocessor in the FPGA is doing the software to read the temperatures, figure alarms and do some fan control. It is still performing the sensor reads once per second. So it does not appear to have locked up. Maybe it's something between the SPI pins on the FPGA and the internal logic and the path to the Picoblaze?

Chipscope shows that all high alarm thresholds are set in this error state: high, very high, and critical. I can place a jumper and bypass the critical reset, to allow software to boot up, and I can check for the error state by looking for the alarm bits to be set. The Picoblaze writes out the temperatures to some registers, and these look correct, even in the error state. The values match the SPI signals from one reading to the next.

Is the Picoblaze getting confused? The first thing it does at FPGA configuration is to read out the temperature set points from a block RAM into its internal scratchpad. I'm realizing that, while I provided a register bit to allow software to hit the Picoblaze reset in case a reconfiguration is needed, it is not normally asserted at startup. So is this a problem of the RAMs not being quite settled right at the end of FPGA configuration? In any case, it seems like good practice to have a reset asserted right out of configuration to make sure we are starting in a good, known state.

Resetting the Picoblaze makes these persistent alarms go away and everything is back to normal.

The next experiment: perhaps have Picoblaze read out some data from the block RAM, then write back what it thinks it got. See if bad data is ever written back. That would suggest a root cause. Also, I've dug through the Virtex 4 data sheets to see if there is a time after the DONE bit goes active that the RAMs may not be ready. So far I haven't found a mention of this.

Error Correction Coding Receiver - Part 3

For coding schemes that can correct more than one error, things get more complicated. Instead of one syndrome vector, there will be 2t equations, where t is the number of correctable errors. A method called the Berlekamp-Massey algorithm is used to solve this system of equations to create an error locator polynomial.

Next, the roots of this polynomial must be found to indicate the location of up to t errors. Once these locations are known, the corrupted bits can be fixed.

A good description and example can be found here: [pdf]

I will attempt to write some code to implement the 31,16 BCH code that can correct up to 3 errors. There are 16 message bits and 15 parity bits which together make up a 31-bit codeword. It uses a polynomial x^5 + x^2 + 1 which generates a field of 32 elements. See the table starting on page 12 of the above link.

To implement this in hardware, a couple of math functions are needed. One is the mutiplying of primitive coefficients. This can be done by representing the coefficients as exponents, and they are multiplied by adding the exponents. For example, to multiply alpha^5 times alpha^11, add 5 and 11. This must be done mod 31 for this code, since any higher exponents are equivalent to the (mod 31) of that exponent. It is not very efficient to do a (mod 31) function in logic, and in any case, it is often not synthesizable with the mod operator (% symbol in Verilog.) A lookup table that handles adding and subtracting (mod 31) is fairly efficient and can be done in 22 slices on a Xilinx Virtex4 device. A result can be returned in one clock cycle.

Another operation is addition, which is done bitwise modulo 2. This is a simple XOR operation, but must be done on the tuple form of the coefficients. Therefore it is useful to have another lookup table that converts between the exponent and tuple forms. This can be realized in 11 slices of a Virtex4 device. For example, alpha^7 is equivalent to alpha^4 + alpha^2 and can be represented as binary 10100.

Error Correction Coding Receiver - Part 2

The first thing needed to decode a linear block code in hardware is a Linear Feedback Shift Register (LFSR). To implement this in programmable logic, a generic block such as that shown below can be written. It is easily customizable for different generator polynomials by adding registers as needed, and by changing the generic parameter that describes the p0lynomial g, with the most-significant degree on the left. This example shows the polynomial

x^5 + x^4 + x^3 + 1.

The term x^5 is implied in the generic parameter since the length of the register is 5. Messages are shifted in and out most-significant-bit first (where the highest bit is the coefficient of the highest degree term in the polynomial.)

This code block has a mode with feedback enabled, and a shift-only mode for shifting out the result.

module lfsr(
   input    rst_n,
   input    clk,
   input   d,
   input    en,
   input   calc_shft_n,
   output    q
);

reg [4:0] shift;

parameter g = 5'b11001;


assign q = shift[4];

always @(posedge clk or negedge rst_n)
    if (!rst_n)
        shift <= 5'b00000;
    else
        if (en)
            if (calc_shft_n) begin
                shift[0] <= d ^ shift[4];
                shift[1] <= shift[0] ^ (shift[4] & g[1]);
                shift[2] <= shift[1] ^ (shift[4] & g[2]);
                shift[3] <= shift[2] ^ (shift[4] & g[3]);
                shift[4] <= shift[3] ^ (shift[4] & g[4]);
            end
            else begin
                shift[0] <= d;
                shift[1] <= shift[0];
                shift[2] <= shift[1];
                shift[3] <= shift[2];
                shift[4] <= shift[3];
            end
endmodule 

Error Correction Coding Receivers - Part 1

Error correction coding is a method of encoding a message for transmission over a noisy channel so that the message can be correctly received even if it has been corrupted by up to some number of errors. A good introduction can be found in a text on digital communications, such as
Digital Communications Fundamentals and Applications by Bernard Sklar, which is available on scribd. This text introduces the overall idea of error correction coding, and some important concepts such as Hamming distance, block codes, and generator polynomials. But it only scratches the surface. When it comes to a practical implementation, a more rigorous algebraic description is needed.

A Hamming code is fairly simple to decode. It is structured to be able to correct one error per message block. The encoded message is decoded by running it through a linear feedback shift register (LFSR) described by a certain generator polynomial. The remainder is the contents of the shift register, and this is called the syndrome. The syndrome maps to a location in the encoded message where a bit error occurred. If no errors were detected, the syndrome will be zero. In hardware, this can be realized with a Meggitt decoder. A good description of such a decoder can be found here [pdf].

More challenging is a decoder that can detect multiple errors, such as for a BCH code. The texts on this delve deeply into abstract algebra, which presents a challenge to someone who is more engineer than mathematician. Fortunately the problem has been reduced to an algorithm that should work for any BCH code, and this can be realized in hardware. Stay tuned for Part 2.

CRC Calculators

Here are some good links on CRC (cyclic redundancy check). Online calculators are good for checking your logic design. There are also some good descriptions of how CRC works.

http://www.zorc.breitbandkatze.de/crc.html
A calculator that includes CRC-CCITT, CRC16, CRC32 presets. Arbitrary lengths, initial value and final XOR value.

http://www.lammertbies.nl/comm/info/crc-calculation.html
Good mathematical explanation and calculator with outputs using several popular methods.