Browse Prior Art Database

COMPUTATIONALLY EFFICIENT BIT ERROR GENERATOR

IP.com Disclosure Number: IPCOM000007527D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2002-Apr-03
Document File: 5 page(s) / 207K

Publishing Venue

Motorola

Related People

Donald Newberg: AUTHOR [+2]

Abstract

It is at times desired to generate random bit streams in a real-time DSP for the purpose oftesting digital systems. While data that has an equal num- ber of ones and zeroes is easy to produce, a bit stream with a fixed bias is often needed to model a known BER condition. This type of data is useful for exer- cising processes whose performance is effected by the number of bit errors. For practical reasons, it is desired that the bit patterns do not repeat over any realistic time Frame and be computationally efficient.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 5

M-ROLA Technical Developments

8

COMPUTATIONALLY EFFICIENT BIT ERROR GENERATOR

by Donald Newberg and Brad Hiben

  It is at times desired to generate random bit streams in a real-time DSP for the purpose oftesting digital systems. While data that has an equal num- ber of ones and zeroes is easy to produce, a bit stream with a fixed bias is often needed to model a known BER condition. This type of data is useful for exer- cising processes whose performance is effected by the number of bit errors. For practical reasons, it is desired that the bit patterns do not repeat over any realistic time Frame and be computationally efficient.

  This type of bit stream is generally created by running a random number generator to produce an integer value which is then compared against a threshold. If the result is below the threshold, the output bit is set to be a 0, otherwise the output bit is set to be a 1. The threshold can therefore be adjusted to produce the desired bias of l's to 0's. A random number generator that can run for several days before repeating, however, generally requires

an LFSR (linear feedback shift register) implemen- tation. Each iteration of an LFSR requires many instruction cycles to produce a single output bit. Because the desired integer value is made up of a large number of bits to obtain good resolution, this method is not very efficient for real time processes.

  Instead of generating a random real number to compare against a threshold, it is possible to pro- duce the desired output bit stream by performing a number of AND and XOR operations on the bits of the LFSR. In this manner, each new output bit requires only one iteration of the LFSR plus some combinational logic calculations. The probability that the output of an AND gate is a 1 is p0 = p, l p2, where pi and p2 are the individual probabilities that the two input bits are a 1. In a similar manner, the probability that the output of an exclusive-OR gate will be a 1 is p, l (1 - p2) + p2
l

(1 - p,).

Table 1: Truth Table for Gates

I Y 1 xANDy 1 xXORy ~

0 I 0 I 0 I' 0 I 1 0 1 ;

1 I 0 I 0 I 1 1 1 1 0 1

  Starting with these relationships, a bit stream with an arbitrary bias is generated by first combin- ing the bits of the LFSR using a number of AND and OR gates to get several intermediate bit streams, each with its own bias. These intermediate streams are again combined using other AND and OR gates to get a second set of intermediate bit streams, again with their own individual biases. Proceeding in this fashion, an output bit stream with the desired bias can be generated (with reasonable accuracy) using the correct number and combination of gates. This is best illustrated using an example that was implemented in sollware and tested with a nominal 10% BER.

  The random bit stream was generated by a 64-bit maximal length LFSR,~ whose sequence does not repeat for 264 = 18.45E It 18 bits. An implementa- tion was designed that generates the next twelve out- put states in a sing...