1
$\begingroup$

I want to know how I can find the type (algorithm) of a binary sequence at hand.

For instance, I'd like to know whether the following (binary) sequence is m-sequence, Barker, Gold, etc.

AC DD A4 E2 F2 8C 20 FC (hex) = 1010110011011101101001001110001011110010100011000010000011111100 (binary)

$\endgroup$

2 Answers 2

3
$\begingroup$

There are not that many low order Barker Code sequences, so it would be feasible to cross-correlate the sequence against a library of Barker codes to see if there are any direct matches.

As for determining a possible m-sequence or Gold Code sequence, the Berlekamp-Massey algorithm is an excellent choice. This algorithm can be used to determine if the sequence can be generated from a Linear Feedback Shift Register (LFSR), which covers the case of an M-Sequence and Gold Code. For the case of an M-Sequence the polynomial as expressed by the feedback coefficients in the LFSR is an irreducible primitive polynomial in GF(2), which means the resulting sequence is the longest possible without repeating (given an Nth order polynomial generator, the sequence is $2^N-1$ long).

For the case of a Gold Code, the sequence is typically generated by summing two LFSR's together of equal order, each using a different irreducible and primitive polynomial that I will refer to as $G1$ and $G2$. If the output of one of the generators is shifted prior to summing, a different and nearly orthogonal code will be generated. Thus for $N$th order polynomials, which each on their own can generate a $2^N-1$ sequence before repeating; we have up to that many shifts that can be applied before adding the two outputs. This means there are $2^N-1$ possible unique codes, each themselves of length $2^N-1$ that can be generated. Interestingly, and for purposes of using the Berlekamp-Massey algorithm, the same result can be done with a single LFSR that is twice as long (twice the order) as the original LFSR's that were summed, and using one polynomial that is the product of $G1$ and $G2$ (convolve the coefficients in GF(2)). Thus the resulting LFSR is not an maximum length sequence, as the polynomial in this case is obviously reducible (as its factors are $G1$ and $G2$). By changing the seed (starting values), we can select which of the $2^N-1$ possible Gold Code sequences our single LFSR will generate.

If the code sequence hasn't been data modulated, meaning the same code repeats once it reaches it's maximum length, then the code length can be determined through autocorrelation, and the resulting polynomial order as determined by the Berlekamp-Massey algorithm can reveal if the code can be generated with a maximum length LFSR (and therefore an m-sequence), or, if the repetition rate is much shorter, then possibly a Gold-Sequence as detailed above. If the sequence does repeat at a shorter interval than the polynomial order, this means the polynomial can be factored into smaller polynomials (and that can be done using this approach) with the resulting generator created potentially as a sum of those individual LFSR's (such as a Gold Code).

My Matlab Code for the Berlekamp-Massey Algorithm is below:

function gen=berlmass2(v) 
    % gen = berlmass2(v)
    % v: row vector of values from a LFSR sequence, at 
    % least 2N long, where N is the anticipated order of the
    % polynomial generator.
    %
    % Implements the Berlekamp-Massey Algorithm which
    % computes the minimum polynomial GEN from linear
    % recurring sequence V over GF(2) . 
    % GEN is a polynomial in ascending order, i.e.,
    % GEN = [gen_0 gen_1 gen_2 . . . ] represents
    % GEN(X) ¦ gen_0 + gen_l X + gen_2 X^2 + ....
    % 
    % Written by Dan Boschen 2012
    %
    % Reference: "Finite Fields", Rudolf Lidl, Harold 
    % Niederreiter, Addison-Wesley Publishing Co., 1983
    % pp 439-441
    %

    p=2;    %GF(2) only

    if ~isempty([find(v~=floor(v)), find(v<0), find(v>=p)])
        error('The input vector must be in GF(2)')
    end;

    v-v(:)' % ensure row vector
    len=length(v);
    
    % preallocate vectors with initial condition
    g= [1 zeros(1, len-1)];   
    h= [0 1 zeros(1,len-2)];   
    m= 0;
 
    for n = 1:len
        a1= g(1:n);
        a2= fliplr(v(1:n));
        b = rem(sum(a1.*a2),p);
        mb(n,1)=m;    
        mb(n,2)=b;    
        gold=g;
        bvec=b.*ones(1,len);
        g=mod(g-bvec.*h,p);
        if and((b~=0),(m>=0))
            binv=1./b;
            binvec=binv.*ones(1,len);
            h= binvec.*[0 gold(1:len-1)];
            hd(n+1,:)=h;
            m=-m;
        else
            h=[0 h(1:len-1)];
            m=m+1;
        end
    end
    order= floor(len/2 + 1/2 - m/2);
    gen = g(1:order+1);
end

For example, if the sequence was 1 1 1 0 0 0 1 0, we would use the function gen=berlmass2([1 1 1 0 0 0 1 0]) and the returned polynomial would be gen = [1 0 0 1 1], which is $1+x^3+x^4$.

$\endgroup$
2
$\begingroup$

Most sequences don't have a "type" of any kind, meaning that they have very little or no linear structure that might allow the sequence to be generated why a relatively short linear feedback shift register or LFSR. This is effectively the meaning of what is known as the Chaitin complexity, or Kolmogorov complexity or Solomonoff-Kolmogorov-Chaitin complexity of a sequence.

For most sequences $s$ of length $\ell$, the shortest program that can print $s$ is of length $\ell+c$ for some positive constant $c$

In effect, for most sequences, we can do little better than just store $s$ in memory and print it out: the $\ell+c$ is. in essence, the length of the program

main() { printf("Hello, world\n") }

that prints the sequence

Hello, world

not by generating it via a secret recipe but just storing it an printing it out.

Now, given a sequence $s$, we can try using the Berlekamp-Massey algorithm to find the shortest LFSR that generates $s$. This is described in Dan Boschen's answer, and I will only give a bit ot explanation about what the algorithm is doing. It is an iterative algorithm that iteratively produces LFSRs that generate the first bit, then their first two bits, then the first three bits, and so on. At the beginning of the $N$-th iteration, we already have an LFSR that generates $s_0, s_1, s_2, \cdots, s_{N-1}$. Let $d$ denote the difference between $s_N$, the $N$-th bit of the given sequence for which you are synthesizing the LFSR, and the bit computed by the LFSR that you have synthesized thus far. If $d=0$, the bit produced by the current LFSR is the same as the bit in the given sequence and so the current LFSR, which is guaranteed to produce $s_0, s_1, \ldots, s_{N-1}$, need not be changed: it is producing $s_N$ also. "If it ain't broke, don't fix it!" On the other hand, if $d \neq 0$, then the current LFSR needs to be updated, that is, we need to find the shortest LFSR that produces not just $s_0, s_1, \ldots, s_{N-1}$ but also $s_N$. How to go about doing this is the crux of the Berlekamp-Massey algorithm. Note that it is easy to find an LFSR that will produce $s_0, s_1, \ldots, s_{N}$: the trick lies in finding the shortest LFSR that will do so.

If the given sequence $s$ has been produced (or is producible) by an LFSR of length $L$, the Berlekamp-Massey algorithm finds this LFSR after it has examined $2L$ bits of $s$. If more than $2L$ bits of $s$ are available, further iterations have discrepancy $0$ and so the LFSR undergoes no further modifications. But, as noted at the beginning of this answer, most sequences are not generatable by short LFSRs, and very often the LFSR produced by the Berlekamp-Massey algorithm has length comparable to the sequence length; in effect, "Hello, world" in hardware instead of in software such as C or MATLAB or Python....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.