Technique for high speed PRBS generation
View Patent ↗A method and a generator are described for high speed generation of an S-bit long pattern of a PRBS sequence to be periodically burst on to a bus of width S. The technique provides the calculation time being independent from the width S of the bus, and comprises calculation of all S bits of the PRBS pattern separately and in parallel by using previous PRBS patterns stored in a memory. For each bit to be generated, the generator performs a constant number N of logical operations require(by a polynomial defining the PRBS sequence.
1. A method for high speed generating an S-bit long pattern of a PRBS sequence, to be periodically burst on to a bus of width S, the method comprising:
calculating all S bits of a new S-bit long PRBS pattern separately and in parallel, said step of calculating comprising:
using previously generated PRBS patterns stored in a memory; and
performing, for each bit to be generated, one and the same number N of logical operations required by a given polynomial, so that the calculation time is independent from the width S of the bus, wherein:
S- is an integer being equal to a number of bits in a PRBS pattern and to the width of the bus measured in bits;
N—is an integer being no less than the minimal number w−1 of logical operations “exclusive OR” (XOR), where w is the number of terms in the given polynomial.
2. The method according to claim 1 , wherein the number N of logical operations is the minimal number of logical operations “exclusive OR” (XOR) being equal to w−1, where w is the number of terms in the given polynomial.
3. The method according to claim 1 , wherein the minimal time required for calculation the PRBS pattern is O(logw), where w is the number of terms in the given polynomial and O is constant.
4. The method according to claim 1 , wherein the step of calculating comprises:
for each bit of the new PRBS pattern to be calculated and currently fed on to a corresponding bit of the S-width bus, using bits of the previously generated PRBS patterns stored in the memory, calculating each bit of the new PRBS pattern according to the following equation:
b
i
=
∑
0
≤
j
<
w
⊕
M
i
-
2
t
·
n
j
,
(
3
)
where
w—is the number of terms in the given polynomial;
b i —running number of a bit of the S-width bus and of a corresponding bit of the new PRBS pattern;
M 1 —running number of a bit of the memory;
t—retrospective index, for choosing an appropriate bit of a previously generated PRBS pattern stored in the memory;
n j —index of complexity of the given polynomial.
5. The method according to claim 4 , comprising selecting different retrospective indexes t for calculating different bits of the bus.
6. A generator for generating an S-bit long pattern of a PRBS sequence to be periodically burst on to a bus of width S. the generator comprising;
a memory;
a logic circuit capable of obtaining all bits of a new-S-bit long PRBS pattern separately and in parallel by using previously generated PRBS patterns stored in the memory and performing for each bit of the new pattern to be generated one and the same number N of logical operations required by a given polynomial, thus achieving a shortened clock period of the generator, being independent from the width of the bus, wherein:
S- is an integer being equal to a number of bits in a PRBS pattern and to the width of the bus measured in bits;
N—is an integer being no less than the minimal number w−1 of logical operations “exclusive OR” (XOR), where w is the number of terms in the given polynomial.
7. The generator according to claim 6 , wherein the memory comprises a plurality of shift registers for respectively storing the previously successively generated S-bit PRBS patterns;
the plurality of shift registers comprising a bottom register and a top register connected to the bus, and being capable of parallel shifting of information upon introducing a “freshest” PRBS pattern into the top register from the bus, so that an “oldest” PRBS pattern is erased from the bottom register of the memory; wherein the the logic circuit comprises:
S sets of N XOR means for obtaining the new S-long PRBS pattern, wherein said N XOR means is provided per each particular bit of said new PRBS pattern to be fed to the bus, for creating the value of said particular bit based on bits of the previous PRBS patterns stored in the memory; and
a clock for synchronizing operation of the XOR means of all the bits thereby obtaining said new PRBS pattern, transmitting it via the bus and shifting it into the top register of the memory.
8. The generator according to claim 6 , wherein the number N is the minimal number being equal to w−1, where w is the number of terms in the given polynomial.
9. The generator according to claim 6 , wherein said stored bits are respectively selected for each bit of the S-width bus according to the following equation:
b
i
=
∑
0
≤
j
<
w
⊕
M
i
-
2
t
·
n
j
,
(
3
)
where
w—is the number of terms in the given polynomial;
b i —running number of a bit of the S-width bus and of a corresponding bit of the new PRBS pattern;
M i —running number of a bit of the memory;
t—retrospective index, for choosing an appropriate bit of a previously generated PRBS pattern stored in the memory;
n j —index of complexity of the given polynomial.
10. The generator according to claim 9 , wherein different retrospective indexes t are selected for calculating different bits of the bus.
11. The generator according to claim 6 , wherein capacity C of the memory is selected according to the following formula:
c= 2 l m ·n w-1 (6)
wherein
w—is the number of terms in the given polynomial;
t—retrospective index, for choosing an appropriate bit of a previous PRBS pattern in the memory;
n j —index of complexity of the given polynomial t m —is the minimal retrospective index calculated according to:
t
m
=
⌈
log
2
s
n
0
⌉
.
(
5
)
12. The generator according to claim 11 , wherein different retrospective indexes t are selected for calculating different bits of the bus, and wherein capacity C′ of the memory is selected as follows:
c′=c −2 t m −1. (7)
13. A method for high speed generating an S-bit long pattern of a PRBS sequence, the method comprising the following steps:
preliminarily storing, in a memory, a number of previous successively generated S-bit long PRBS patterns in the order of their generation, and performing parallel shift of the stored information upon introducing a freshest PRBS pattern into the memory;
creating, separately and in parallel, each of S bits of a new S-long PRBS pattern, so that each particular bit of said new PRBS pattern is obtained based on a given polynomial and by applying one and the same number N of logical operations to specific bits of the previous PRBS patterns stored in the memory;
synchronizing said N logical operations performed for obtaining different bits of the new S-long PRBS pattern, to generate all the bits of said pattern simultaneously, and
issuing the generated new S-long PRBS pattern and storing said pattern in the memory as the freshest PRBS pattern, wherein:
S- is an integer being equal to a number of bits in a PRBS pattern;
N—is an integer being no less than the minimal number w−1 of logical operations “exclusive OR” (XOR), where w is the number of terms in the given polynomial.
14. A generator for generating an S-bit long pattern of a PRBS sequence to be periodically burst on to a bus of width S, the generator being capable of calculating S bits of a new S-bit long PRBS pattern separately and in parallel by using previous successively generated S-bit long PRBS patterns; the generator comprises:
a memory including a plurality of shift registers for respectively storing the previous successively generated S-bit long PRBS patterns; the plurality of shift registers comprises a bottom register and a top register and is capable of performing parallel shift of information there-between upon introducing a freshest PRBS pattern into the top register;
S sets of N logical means for generating the new S-long PRBS pattern, wherein each of said sets are capable of generating a particular bit of said new PRBS pattern based on a given polynomial by applying N respective logical operations to specific bits of the previous successively generated S-bit long PRBS patterns stored in the memory;
a clock for synchronizing operation of all said logical means for simultaneously generating all bits of said new S-long PRBS pattern; and
means for transmitting the generated new S-long PRBS pattern to the bus, and for storing said pattern in the memory as the “freshest” PRBS pattern, wherein:
S- is an integer being equal to a number of bits in a PRBS pattern and to the width of the bus measured in bits;
N—is an integer being no less than the minimal number w−1 of logical operations “exclusive OR” (XOR), where w is the number of terms in the given polynomial.