[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1031.0. "Practical and theoretical comm problem" by STKHLM::LINNELL (Jan Linnell) Wed Feb 22 1989 05:20

    This is a practical problem with combinatorical implications.
    
    In a reply for a RFP I have to specify all overhead in a file
    transfer using FTP/TCP/IP/X.25.
    
    The problem came on the lowest level: bitstuffing on link layer (LABP).
    
    The algoritm for bitstuffing is very simple:
    	Avoid getting a flag (01111110) by adding a 0 after n=5
        consecutive 1:s in the OUTPUT-streem.
        Example 0011111110 -> 00111110110.
    
    My first (silly) guess was that given a 'long' random bit streem
    (P(1) = P(0) = 1/2, independent bits) would give a mean overhead
    slightly above 1/2^n (observe that this problem does not exactly fit
    into the the theory of runs, because the sequence is actually modified
    when a bitstuffing is done).
    
    'Simulations' has though convinced me that the correct overhead is
    exact 1/2n !!!. (Synchronous and asynchrounous comm have the same 
    overhead when n=5 !!! )
    
    Question:
    	Can somebody prove this (on different levels).
    
    	Given a random input streem of length l
    
    	- What is the distribution of nr of bitstuffs?
    
        - What is the limit of the meen overhead E[bitstuffs]/l
          when n -> oo?
    
    I would guess that like many combinatorical problems that it could exist
    a short proof.
    
    /jan
T.RTitleUserPersonal
Name		DateLines
1031.1The theory is easyPOOL::HALLYBThe smart money was on GoliathWed Feb 22 1989 15:2714
    This sounds like a Richie Lary question.
    
    Jan, can you clarify one thing for me?  How many flags are in a
    message?  If I present N bytes to the datalink, will it generate
    1 flag?  2?  O(N)?
    
    It seems to me that the stuffer would need exactly the sequence
    0-1-1-1-1-1 before taking action.  The probability of this happening
    is of course 1/64, far less than the 1/10 or 1/9 of asynch comms.
    
    Why are you seeing 1/10?  Perhaps your bit stream is not as random as
    you think it is.  Are you *sure* your simulation used random numbers?
    
      John
1031.2STKHLM::LINNELLJan LinnellWed Feb 22 1989 17:139
    A assume the input stream to be random (sample of a Bernoulli sequence
    etc). The algoritm should absolutly not produce ANY flags.
    
    The random generator is VERY good (random() in Ultrix.)
    
    Yes, the stuffer puts in a 0 exactly after 011111 but in the OUTPUT
    stream, the first zero could be an earlier stuffing.
    
    /jan
1031.3random => p(0) = p(1) = 1/24GL::GILBERTOwnership ObligatesThu Feb 23 1989 19:1630
    After the initial 5 input bits, the finite-state machine is in one of
    six states Si, i=0,...,5.  Si means that the immediately preceding i
    output bits were 1s, and the bit before them was a 0.
    
    We have the state transition table:
    
    	State	in=0	in=1
    	  S0	S0	S1
    	  S1	S0	S2
    	  S2	S0	S3
    	  S3	S0	S4
    	  S4	S0	S5
    	  S5	S0	S1
    
    Now let p(Si) be the probability that the machine is in state Si, when
    run on a random stream of input bits.  Now regardless of the current state,
    the probability that the next state is S0 is 1/2 (since p(S0) = p(S0)/2
    + p(S1)/2 + ... + p(S5)/2 = 1/2).  Now, in turn:
    
    	p(S0) = 1/2
    	p(S1) = p(S0)/2 + p(S5)/2 = 1/4 + p(S5)/2
    	p(S2) = p(S1)/2 = 1/8 + p(S5)/4
    	p(S3) = p(S2)/2 = 1/16 + p(S5)/8
    	p(S4) = p(S3)/2 = 1/32 + p(S5)/16
    	p(S5) = p(S4)/2 = 1/64 + p(S5)/32
    
    So p(S5) = (32/31)*(1/64) = 1/62.
    
    Given that 1/62 of the input bits will cause a transition to S5, an
    input stream of L bits should be expected to grow to (63/62)*L bits.
1031.4ThanksSTKHLM::LINNELLJan LinnellFri Feb 24 1989 11:5313
Re: .-1

Thanks alot, the method was exactly what I was searching for.
Handling the problem as a Markov chain in this manner makes it easy
to generalize the problem to n bits (1/(2^(n+1) -2)), and to calculate
the whole transient behavior and any the distributions I wanted.

(I've learnt several lessons from this)

(I've also 'verified' the results by a new and hopefully more correct
'simulation')

/jan