| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1062.1 | Knuth or Golomb | CADSYS::COOPER | Topher Cooper | Wed Apr 19 1989 12:34 | 13 |
| I'm about 98% sure that this question is answered in Knuth, vol II, but
I don't have a copy here to check.
The "bible" in this area is "Shift Register Sequences" by Solomon W.
Golomb. It analyzes the problem, and a host of related ones, in
great depth and with a fair amount of rigour. You should be able to
obtain it by DEC internal inter-library loan, since at least one site,
HLO, has a copy.
If you just want the answer to your question with a minimum of extras,
however, use Knuth.
Topher
|
| 1062.2 | I'll check later... | RAMBLR::MORONEY | Sign your life away, on the dotted line... | Wed Apr 19 1989 19:45 | 5 |
| The TTL Cookbook covers these (as pseudo-random shift registers) briefly, and
they do have a table of connections for maximum-length sequences for register
lengths from 2 to 31.
-Mike
|
| 1062.3 | coding theory textbooks another source | CTCADM::ROTH | If you plant ice you'll harvest wind | Thu Apr 20 1989 08:01 | 10 |
| Books on coding theory are another source of information. In particular
Peterson's book (MIT press) and Blahut's book - both titled "Theory of
Error Correcting Codes" or some such - are very easy to understand.
A classic paper by N. Zierler, "Linear Recurring Sequences" appeared in
one of the SIAM journals around 1960 - it's probably a little hard to
read without some algebra background but has lots of neat stuff so would
be worth looking up.
- Jim
|
| 1062.4 | Thanks for you help. | WIENER::BUTTON | Derek BUTTON @VNO/FS-OPS | Mon Apr 24 1989 08:10 | 8 |
| Thank-you, Topher, Mike and Jim; I got some good pointers and have
started to follow up.
The buzz-word "pseudo-random" (from Mike, I think), rang a very
distant bell: something to do with a modulation technique for
high capacity communications links/satellite comms or...? Who
can get closer?
Derek.
|
| 1062.5 | | RAMBLR::MORONEY | Sign your life away, on the dotted line... | Mon Apr 24 1989 14:42 | 7 |
| re .4:
The "pseudo-random" comes from the fact that if you look at a short sequence
of bits from them they appear to be random. Of course, longer sequences
show a pattern.
-Mike
|
| 1062.6 | | RAMBLR::MORONEY | It works!! | Sun Apr 30 1989 15:30 | 47 |
| re .0:
> So: My problem. Does anyone have a formula or suggestion
> how I can calculate which element (x) will give me an
> M-Sequence ? For some registers, there are more than one
> solution.
Maybe this will help: For a shift register of length "n", the following
connections give a maximal-length sequence:
n XOR inputs
--------------
2 1 and 2
3 2 and 3
4 3 and 4
5 3 and 5
6 5 and 6
7 6 and 7
9 5 and 9
10 7 and 10
11 9 and 11
15 14 and 15
17 14 and 17
18 11 and 18
20 17 and 20
21 19 and 21
22 21 and 22
23 18 and 23
25 22 and 25
28 25 and 28
29 27 and 29
31 28 and 31
For any of the above sequences, a second sequence which is the first sequence
"backwards" can be formed by counting from the other end when making the first
connection. For example, for the sequence of length 31, a maximal-length
sequence can be formed by connecting the XOR gate's input to bits 3 and 31.
This is the same sequence as the 28-31 sequence, except it runs backward.
Adding an inverter to the feedback path gives an inverted sequence.
Maximal-length sequences of lengths 8, 12, 13, 14, and 16 can be obtained
by tapping the sequence at 4 points and XOR'ing them together with 3 XOR gates.
Sequences of nearly full-length of lengths 24, 26, 27, 30 can be obtained with
a single XOR gate.
-Mike
|
| 1062.7 | | AITG::DERAMO | Daniel V. {AITG,ZFC}:: D'Eramo | Mon May 01 1989 11:20 | 19 |
| I thought I remembered reading that for something like
n XOR inputs polynomial
-------------- ------------------
2 1 and 2 x^2 + x + 1
3 2 and 3 x^3 + x^2 + 1
4 3 and 4 x^4 + x^3 + 1
5 3 and 5 x^5 + x^3 + 1
[...]
31 28 and 31 x^31 + x^28 + 1
to give a sequence of length 2^n - 1, it was necessary and
sufficient that the corresponding polynomial be irreducible
as a polynomial over the two element field of integers modulo
two.
Can anyone verify/refute this?
Dan
|
| 1062.8 | | KOBAL::GILBERT | Ownership Obligates | Mon May 01 1989 18:29 | 20 |
| re .6:
>Maybe this will help: For a shift register of length "n", the following
>connections give a maximal-length sequence:
>[...]
I noticed that the table was missing entries for n = 8, 12, 13, 14, 16, 19,
24, 26, 27, and 30. For the connections that were listed, I believe the
cycle length is 2**n-1 (I verified this for n <= 20). Here are connections
for maximal-length sequences for some of the other n:
n XOR inputs cycle length
---------------------------------
8 5 and 8 217 = %x000000D9
12 11 and 12 3255 = %x00000CB7
13 10 and 13 8001 = %x00001F41
14 13 and 14 11811 = %x00002E23
16 9 and 16 63457 = %x0000F7E1
19 13 and 19 520065 = %x0007EF81
|