UMAC

2013-08-30T17:21:15Z

164.107.166.104: /* Universal hashing */

A [[binary sequence]] (BS) is a [[sequence]] <math>a_0,\ldots, a_{N-1}</math> of <math>N</math> bits, i.e.

:<math>a_j\in \{0,1\}</math> for <math>j=0,1,...,N-1</math>.

A BS consists of <math>m=\sum a_j</math> ones and <math>N-m</math> zeros.

A BS is a '''[[pseudorandomness|pseudo-random]] binary sequence''' (PRBS) if its [[autocorrelation function]]:

:<math>C(v)=\sum_{j=0}^{N-1} a_ja_{j+v}</math>

has only two values:

:<math>C(v)=
\begin{cases}
m, \mbox{ if } v\equiv 0\;\; (\mbox{mod}N)\\
\\
mc, \mbox{ otherwise }
\end{cases}</math>

where

:<math>c=\frac{m-1}{N-1}</math>

is called the ''duty cycle'' of the PRBS, similar to the [[duty cycle]] of a continuous time signal.

A PRBS is 'pseudorandom', because, although it is in fact deterministic, it seems to be random in a sense that the value of an <math>a_j</math> element is independent of the values of any of the other elements, similar to real random sequences.

A PRBS can be stretched to infinity by repeating it after <math>N</math> elements, this in contrast to most random sequences, such as sequences generated by [[radioactive decay]] or by white noise, that are 'infinite' by nature. The PRBS is more general than the [[maximum length sequence]], which is a special pseudo-random binary sequence of N bits generated as the output of a linear shift register. A maximum length sequence always has a 1/2 duty cycle and its number of elements <math>N = 2^k-1</math>. PRBS's are used in [[telecommunication]], [[encryption]], [[simulation]], [[correlation]] technique and time-of-flight [[spectroscopy]].

== Practical implementation ==
Pseudorandom binary sequences can be generated using [[linear feedback shift register]]s.<ref>Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.</ref>

== See also ==
* [[Pseudorandom number generator]]
* [[Gold code]]
* [[Complementary sequences]]
* [[Bit Error Rate Test]]

==References==
{{reflist}}

== External links ==
* http://www.scriptwell.net/correlation.htm

{{Refimprove|date=January 2008}}

[[Category:Pseudorandomness]]
[[Category:Binary sequences]]

formulasearchengine - User contributions [en]

UMAC