Generic Binary Sequence (bsequence)

Keywords: binary sequence bsequence

The bsequence object implements a generic binary shift register and is particularly useful in wireless communications for correlating long bit sequences in seeking frame preambles and packet headers. The bsequence object internally stores its sequence of bits as an array of bytes which handles shifting values even faster than the window family of objects. Listed below is the basic interface to the bseqeunce object:

  • bsequence_create(n) creates a bsequence object with \(n\) bits, filled initially with zeros.
  • bsequence_destroy(q) destroys the object, freeing all internally-allocated memory.
  • bsequence_clear(q) resets the sequence to all zeros.
  • bsequence_init(q,*v) initializes the sequence on an external array of bytes, compactly representing a string of bits.
  • bsequence_print(q) prints the contents of the sequence to the screen.
  • bsequence_push(q,bit) pushes a bit into the back (right side) of a binary sequence, and in turn drops the left-most bit. Only the right-most (least-significant) bit of the input is regarded. For example, pushing a 1 into the sequence 0010011 results in 0100111 .
  • bsequence_circshift(q) circularly shifts a binary sequence left, pushing the left-most bit back into the right-most position. For example, invoking a circular shift on the sequence 1001110 results in 0011101 .
  • bsequence_correlate(q0,q1) runs a binary correlation of two bsequence objects q0 and q1 , returning the number of similar bits in both sequences. For example, correlating the sequence 11110000 with 11001100 yields 4 .
  • bsequence_add(q0,q1,q2) computes the binary addition of two sequences q0 and q1 storing the result in a third sequence q2 . Binary addition of two bits is equivalent to their logical exclusive or , \(\oplus\) . For example, the binary addition of 01100011 and 11011001 is 10111010 .
  • bsequence_mul(q0,q1,q2) computes the binary multiplication of two sequences q0 and q1 storing the result in a third sequence q2 . Binary multiplication of two bits is equivalent to their logical and , \(\land\) . For example, the binary multiplication of 01100011 and 11011001 is 01000001 .
  • bsequence_accumulate(q) returns the 1 s in a binary sequence.
  • bsequence_get_length(q) returns the length of the sequence (number of bits).
  • bsequence_index(q,i) returns the bit at a particular index of the sequence, starting from the right-most bit. For example, indexing the sequence 00000001 at index 0 gives the value 1 .