Calculation of the possible distribution of the dynamic stuff bits in a bit sequence

Question

1.00/5 (1 vote)

See more:

Initial situation:
There is a bit sequence consisting of 13 bits. The first 12 bits can have variable values 𝑥 ∈ [0,1]. The
last (13th) bit always has the value "0".
Bit
Number
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Value x x x x x x x x x x x x 0
If there are 5 equivalent bits in the bit sequence, a bit with the complementary value is inserted
immediately after this subsequence of 5 equivalent bits. This complementary bit is called stuff bit.
For example, in the sequence 0111111100100 one stuff bit have to be inserted after the 6th bit:
Bit
Number
1. 2. 3. 4. 5. 6. SB 7. 8. 9. 10. 11. 12. 13.
Value 0 1 1 1 1 1 0 1 1 0 0 1 0 0
Each stuff bit is included in the next (possible) subsequence. For example in the sequence
1000001111100 two stuff bits after the 6th and the 10th bit will be inserted:
Bit
Number
1. 2. 3. 4. 5. 6. SB 7. 8. 9. 10. SB 11. 12. 13.
Value 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0
The last stuff bit can be inserted after the 13th bit and the highest possible number of stuff bits is
three.
Bit
Number
1. 2. 3. 4. 5. SB 6. 7. 8. 9. SB 10. 11. 12. 13. SB
Value 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1
So there are 4 possible situations:
 no stuff bits are inserted in the output bit sequence
 1 stuff bit is inserted into the output bit sequence
 2 stuff bits are inserted into the output bit sequence
 3 stuff bits are inserted into the output bit sequence

Task description:
An application must be developed which checks all possible sequence combinations from
0000000000000 to 1111111111110. (2^12 combinations are possible.)
Besides, it shall be counted how many combinations are subordinated to which category:
 𝑛0 subsequences without stuff bits
 𝑛1 subsequences with 1 stuff bit
 𝑛2 subsequences with 2 stuff bits
 𝑛3 subsequences with 3 stuff bits

What I have tried:

I tried first the logic but not able to do as 13 bit must be always 0

Posted 16-Sep-20 8:51am

jaswanth chakri

Updated 16-Sep-20 21:08pm

PIEBALDconsult

v2

Add a Solution

Comments

jeron1 16-Sep-20 15:32pm

Can you do this on paper?

CPallini 17-Sep-20 2:56am

"The last stuff bit can be inserted after the 13th bit and the highest possible number of stuff bits is
three."
This doesn't look correct to me. Could you please provide an example?

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2020-09-16T09:23:00

Solution 1

Quote:
An application must be developed

I would expect that is an instruction to you to complete this assignment.

Posted 16-Sep-20 9:23am

Richard MacCutchan

CPallini · Answer 2 · 2020-09-16T21:08:00

Let's try to enumerate the input sequences

//               bit no                      value
// 12 11 10  9  8  7  6  5  4  3  2  1  0
//---------------------------------------     
//  0  0  0  0  0  0  0  0  0  0  0  0  0  =    0
//  0  0  0  0  0  0  0  0  0  0  0  1  0  =    2
//  0  0  0  0  0  0  0  0  0  0  1  0  0  =    4
//  0  0  0  0  0  0  0  0  0  0  1  1  0  =    6
// ...
//  1  1  1  1  1  1  1  1  1  1  1  1  0  = 8190

So you have to deal with all the even number less than 8192.
With a simple loop you may generate all the input sequences.
For each sequence you may count the number of stuff bits by construction, e.g.

// value =   0 =>  0 0 0 0 0 0 0 0 0 0 0 0 0 => 0 0 0 0 0 [1] 0 0 0 0 0 [1] 0 0 0 => 2 stuff bits
// velue = 240 =>  0 0 0 0 0 1 1 1 1 0 0 0 0 => 0 0 0 0 0 [1] 1 1 1 1 [0] 0 0 0 0 [1] => 3 stuff bits

Note (as shown in value = 240), that stuff bits can contribute to the next sequence.

Good luck.