0

11001101111011000011000111001011010011010111011011100011100111101011 the above bit stream should break up into these variable bit packets 11 0011 0111 1011 000011 000111 001011 010011 010111 011011 100011 100111 101011 basically it is a base 3 number represented in base 2 as 2 bits base 2 number of variable length, with a 11 as a stop pattern, as long as you are looking at this 2 bits at a time, can you determine the second list of values from the bit stream I gave at the top part?

John Einem
  • 1

1 Answers1

1

If you're allowed to remember some state between the processing steps, then yes.

Just do the following, assuming that the state bit is $s$ and the current input bits are $b_0$, $b_1$

  1. Append $b_0$ to the output
  2. If $s \land b_0$
    1. Append space to the output
  3. Append $b_1$ to the output
  4. If $\lnot s \land b_0 \land b_1$
    1. Append space to the output
    2. Set $s \leftarrow 0$
  5. Otherwise
    1. Set $s \leftarrow b_1$

Thus, $s = 1$ if the last bist of the previous 2-bit chunk might be the first (but not the second!) bit of a stop pattern. By comparing $s$ and $b_0$, stop pattern which are split between two such chunks are detected and handled appropriately. By comparing $b_0$ and $b_1$, stop patterns within a chunk are detected, and the additional check for $s=0$ ensures that $0111$ isn't decoded to "011 1 " but rather to "011 1". Setting $s$ to $0$ in 4.2 prevents "1110" from being decoded to "11 1 0".

Here's an example. Say the input is $$ 011110001110100110 \text{.} $$ The processing then does this $$ \begin{array}{cc|ll|ll|ll|ll|ll|ll|ll|ll|ll} b_0 &b_1 & 0&1 & 1&1 & 1&0 & 0&0 & 1&1 & 1&0 & 1&0 & 0&1 & 1&0 \\ s_{\textrm{in}} &s_{\textrm{out}} & 0&1 & 1&1 & 1&0 & 0&0 & 0&0 & 0&0 & 0&0 & 0&1 & 1&0 \\ \hline && 0&1 & 1.&1& 1.&0& 0&0 & 1&1.& 1&0 & 1&0 & 0&1 & 1.&0 \end{array} $$ where the last line is the output, and dots represent spaces.

Notation-wise, $\lnot$ means logical not, i.e. $\lnot x$ is true if $x=0$, and $\land$ means logical and, i.e. $x \land y$ is true if $x=1$ and $y=1$. Logical or (which isn't used here) would be written as $x \lor y$ and would be true if $x=1$ or $y=1$.

fgp
  • 21,050
  • well thanks, not sure what this symbol ^ means as in: "If s^b0 " in this context, can you enlighten me please?? if I could just get that I Think I can understand the rest.. thanks – John Einem May 26 '13 at 10:24
  • It means "logical and". In other words, $s \land b_0$ is true if $s=1$ and $b_0=1$. – fgp May 26 '13 at 11:02
  • Btw, you get that symbol with \land in LaTex and MathJax – fgp May 26 '13 at 11:03
  • OK thank you very much, would what you are describing be processing the data one bit at a time?... because the packet size or minimum number of bits would be 2 bits, because you would have to look for the stop bit pattern of 11 , to determine that the end of the pattern has been reached, if you only look at one bit at a time as It would seem your suggestion suggests, what's to prevent it from finding the first "11" pattern that shows up.. such as the decoding of 000111, whats to prevent it from decoding as 00011?? I guess the the fact that 00011 is only 5 bits. – John Einem May 26 '13 at 11:15
  • @JohnEinem Just FYI, I just edited my answers to fix a bug I found upon re-reading it. – fgp May 26 '13 at 11:23
  • @JohnEinem It will decode "000111" as "00011 1", that what your question says it should, no? Otherwise, saying that "11" is the stop-pattern really doesn't make much sense... – fgp May 26 '13 at 11:26
  • @JohnEinem It looks at two bits at a time, that's why it has two inputs $b_0$ and $b_1$. I'll add an example of how it works... – fgp May 26 '13 at 11:29
  • ok thanks a lot... yeah I must be tired... but there is probably more than one way to do the decoding of this type of bit stream of variable bit length "words" you could look at the whole thing two bits at a time and then add the code to the output buffer for as long as the two bits are not 11 , when it encounters a 11 bit pattern append that to the output , then a space or whatever signals the receiver that a new code is coming, if the first pair of values received is 11 then it is done with a complete "word" or command , and then can send that and signal that a new code is on its way. – John Einem May 26 '13 at 11:58
  • let us continue this discussion in chat – John Einem May 26 '13 at 12:13
  • @fpg I hate to say it but 011110001110100110 should decode as 0111 100111 010011 with an extra 0 at the end an incomplete code... – John Einem May 26 '13 at 12:25