Puncturing

Hi,

I've got a simple MATLAB model of a wireless standard that I've been
trying to get to work. So far, I've not had much success.

The problem I have is with puncturing. Basically, I generate a series
of bits for my data stream and then I remove some bits according to
some puncturing pattern. I then reconstitute this data stream by
inserting zeros in the correct places. Note however that there is no
channel as yet in this model; data is simply fed in and fed out. Before
I carry out the puncturing I use a convolutional encoder with
constraint length 7 (for the IEEE 802.11a standard), and after I use a
viterbi decoder with the same polynominal and trace-back depth of 3 (is
this too small? how does one decide on the correct value).
Unforunately, with this combination, I am experiencing a very high bit
rate. It was my understanding that although the system is, in effect,
introducing bit errors into the transmitted bit stream (through
puncturing), the level of error introduced is small enough to be
overcome by the convolutional code applied. So, in this case, I would
expect to see no bit errors introduced after decoding.

Can someone please give me some advice on this matter, or maybe point
out where I might be going wrong?

Best regards,

Stephen

Steve,

>From what i remember the traceback length should be of the order of 5-6
times the constraint length.  I would try that to start with; get the
thing going and then work on shortening if required later on.

col


Steve wrote:
> Hi,
>
> I've got a simple MATLAB model of a wireless standard that I've been
> trying to get to work. So far, I've not had much success.
>
> The problem I have is with puncturing. Basically, I generate a series
> of bits for my data stream and then I remove some bits according to
> some puncturing pattern. I then reconstitute this data stream by
> inserting zeros in the correct places. Note however that there is no
> channel as yet in this model; data is simply fed in and fed out. Before
> I carry out the puncturing I use a convolutional encoder with
> constraint length 7 (for the IEEE 802.11a standard), and after I use a
> viterbi decoder with the same polynominal and trace-back depth of 3 (is
> this too small? how does one decide on the correct value).
> Unforunately, with this combination, I am experiencing a very high bit
> rate. It was my understanding that although the system is, in effect,
> introducing bit errors into the transmitted bit stream (through
> puncturing), the level of error introduced is small enough to be
> overcome by the convolutional code applied. So, in this case, I would
> expect to see no bit errors introduced after decoding.
>
> Can someone please give me some advice on this matter, or maybe point
> out where I might be going wrong?
> 
> Best regards,
> 
> Stephen

> >From what i remember the traceback length should be of the order of 5-6
> times the constraint length.  I would try that to start with; get the
> thing going and then work on shortening if required later on.

Steve,

I think the typical traceback length should be 5 time the constraint
length for a rate 1/2 code.  If you puncture your code, you are
weakening it.  For this reason, you will need to increase your
traceback length to make up for the weaker code.

As suggested above, start at 5 or 6 times the constraint length.
However, instead of shortening it, I would lengthen it until you get
the BER you require.

Let us know how it works out.

Phil

It's not really working, my BER is still very high.

One thing that's bothering me is that by increasing the trace-back
depth I lose more bits from the end of the bitstream. For example, say
I have a 10 bit sequence and I have a trace-back depth of 5, then when
I invoke the vitdec function in MATLAB, it returns a 10 bit vector (the
first 5 bits are zero for the trace-back delay) and not 15 as I
require. How can be obtain the final 5 bits of the sequence? Is it
possible?

Thanks,

Stephen


Phil wrote:
> > >From what i remember the traceback length should be of the order of 5-6
> > times the constraint length.  I would try that to start with; get the
> > thing going and then work on shortening if required later on.
>
> Steve,
>
> I think the typical traceback length should be 5 time the constraint
> length for a rate 1/2 code.  If you puncture your code, you are
> weakening it.  For this reason, you will need to increase your
> traceback length to make up for the weaker code.
>
> As suggested above, start at 5 or 6 times the constraint length.
> However, instead of shortening it, I would lengthen it until you get
> the BER you require.
> 
> Let us know how it works out.
> 
> Phil

Steve,

I'm sorry, i got confused with the input and output bits that you have
described.  If you have a rate k/n encoder, then for every n bits that
you input into the decoder, you should get k bits out.  That's all
there is to it.  What type of decoding are you using with the function?
 DECTYPE=??  I'm pretty sure that it should be 'soft' for the Matlab
function (especially for punctured inputs) and then you need to specify
your number of quantisation bits.

Hope that helps,

col


Steve wrote:
> It's not really working, my BER is still very high.
>
> One thing that's bothering me is that by increasing the trace-back
> depth I lose more bits from the end of the bitstream. For example, say
> I have a 10 bit sequence and I have a trace-back depth of 5, then when
> I invoke the vitdec function in MATLAB, it returns a 10 bit vector (the
> first 5 bits are zero for the trace-back delay) and not 15 as I
> require. How can be obtain the final 5 bits of the sequence? Is it
> possible?
>
> Thanks,
>
> Stephen
>
>
> Phil wrote:
> > > >From what i remember the traceback length should be of the order of 5-6
> > > times the constraint length.  I would try that to start with; get the
> > > thing going and then work on shortening if required later on.
> >
> > Steve,
> >
> > I think the typical traceback length should be 5 time the constraint
> > length for a rate 1/2 code.  If you puncture your code, you are
> > weakening it.  For this reason, you will need to increase your
> > traceback length to make up for the weaker code.
> >
> > As suggested above, start at 5 or 6 times the constraint length.
> > However, instead of shortening it, I would lengthen it until you get
> > the BER you require.
> > 
> > Let us know how it works out.
> > 
> > Phil

>>>>> "Steve" == Steve  <stephenry@gmail.com> writes:

    Steve> Hi,
    Steve> I've got a simple MATLAB model of a wireless standard that I've been
    Steve> trying to get to work. So far, I've not had much success.

    Steve> The problem I have is with puncturing. Basically, I generate a series
    Steve> of bits for my data stream and then I remove some bits according to
    Steve> some puncturing pattern. I then reconstitute this data stream by
    Steve> inserting zeros in the correct places. Note however that there is no
    Steve> channel as yet in this model; data is simply fed in and fed out. Before

You have to insert the right values for the punctured bits.  A zero is
the right value if you are using squared-error metric and your symbols
are +1 and -1.  (Or +M and -M).  If you're using something different,
you need to be more careful with what you insert.

I think the basic idea is whatever you use, you don't want to change
the metric on that branch, so you don't bias the Viterbi to choose one
path over another, just because the bit was punctured.

Ray

c...@hotmail.com wrote:
> Steve,
>
> I'm sorry, i got confused with the input and output bits that you have
> described.  If you have a rate k/n encoder, then for every n bits that
> you input into the decoder, you should get k bits out.  That's all

The other way around. Input bits are k, and output bits are n.

> there is to it.  What type of decoding are you using with the function?
>  DECTYPE=??  I'm pretty sure that it should be 'soft' for the Matlab
> function (especially for punctured inputs) and then you need to specify
> your number of quantisation bits.
>
> Hope that helps,
>
> col
>
>
> Steve wrote:
> > It's not really working, my BER is still very high.
> >
> > One thing that's bothering me is that by increasing the trace-back
> > depth I lose more bits from the end of the bitstream. For example, say
> > I have a 10 bit sequence and I have a trace-back depth of 5, then when
> > I invoke the vitdec function in MATLAB, it returns a 10 bit vector (the
> > first 5 bits are zero for the trace-back delay) and not 15 as I
> > require. How can be obtain the final 5 bits of the sequence? Is it
> > possible?
> >
> > Thanks,
> >
> > Stephen
> >
> >
> > Phil wrote:
> > > > >From what i remember the traceback length should be of the order of 5-6
> > > > times the constraint length.  I would try that to start with; get the
> > > > thing going and then work on shortening if required later on.
> > >
> > > Steve,
> > >
> > > I think the typical traceback length should be 5 time the constraint
> > > length for a rate 1/2 code.  If you puncture your code, you are
> > > weakening it.  For this reason, you will need to increase your
> > > traceback length to make up for the weaker code.
> > >
> > > As suggested above, start at 5 or 6 times the constraint length.
> > > However, instead of shortening it, I would lengthen it until you get
> > > the BER you require.
> > >
> > > Let us know how it works out.
> > >
> > > Phil

Hi Steve,

You may have to call Matlab's vitdec function with the puncturing
pattern as one of the parameters. If you already doing that, just cross
check if you are passing the puncturing pattern in the same manner the
vitdec function needs it to be.

Also, if you can give  a few lines of code showing how you are using
the convenc and vitdec, there are more chances you might get a useful
answer.

Regards,
Prasanna

Prasanna wrote:
> c...@hotmail.com wrote:
> > Steve,
> >
> > I'm sorry, i got confused with the input and output bits that you have
> > described.  If you have a rate k/n encoder, then for every n bits that
> > you input into the decoder, you should get k bits out.  That's all
>
> The other way around. Input bits are k, and output bits are n.
>

Not quite, I think you missed the encoder and decoder switching of
words.  For the ENCODER i input k uncoded bits and get n coded bits
out.  At the DECODER I input n coded bits and get k uncoded bits out.

<snipped>
>
> Hi Steve,
>
> You may have to call Matlab's vitdec function with the puncturing
> pattern as one of the parameters. If you already doing that, just cross
> check if you are passing the puncturing pattern in the same manner the
> vitdec function needs it to be.
>
> Also, if you can give  a few lines of code showing how you are using
> the convenc and vitdec, there are more chances you might get a useful
> answer.

good suggestion.

col

Hi,

I'm using the student version of MATLAB, so it's not quite upto to date
with respect to the commercial versions.

I've looked over the VITDEC function documentation in my version of
MATLAB and there is no reference to puncturing patterns, however in the
on-line version of the documentation there is, which leads me to
believe that this operation is not supported by my version of the
software.

Here is a copy of the code I am working with:

First of all, there is a simple puncturing function that collects input
binary data, punctures it and depunctures it. As far as I'm aware it is
correct:

function [ punctured_data, depunctured_data ] = tmp_puncture( data )

    tx_bin_hdr_data = data;

    N_HDR_CODED_END = 0;

   % Allocate "Bit Stolen Data" vector
            punc_vector_len = ...
                ( length(tx_bin_hdr_data) - N_HDR_CODED_END ) * (2/3);
            tx_data_bin_punc = zeros(1, punc_vector_len);

   % A
            A_idx = setdiff( ...
                [(N_HDR_CODED_END + 1):2:length(tx_bin_hdr_data)], ...
                [(N_HDR_CODED_END + 5):6:length(tx_bin_hdr_data)] );
            tx_data_bin_punc([1:2:length(tx_data_bin_punc)]) = ...
                tx_bin_hdr_data(A_idx);

   % B
            B_idx = setdiff( ...
                [(N_HDR_CODED_END + 2):2:length(tx_bin_hdr_data)], ...
                [(N_HDR_CODED_END + 4):6:length(tx_bin_hdr_data)] );
            tx_data_bin_punc([2:2:length(tx_data_bin_punc)]) = ...
                tx_bin_hdr_data(B_idx);

            punctured_data = tx_data_bin_punc;
            % REMOVE PUNCTURING

            punc_vector_len = ...
                ( length( punctured_data ) - N_HDR_CODED_END ) * (3/2);
            rx_data_bin_depunc = zeros(1, punc_vector_len);

            % A
            A_idx = setdiff( ...
                [1:2:length(rx_data_bin_depunc)], ...
                [5:6:length(rx_data_bin_depunc)] );
            rx_data_bin_depunc( A_idx ) = punctured_data( ...
                [(N_HDR_CODED_END+1):2:length(punctured_data)] );

            % B
            B_idx = setdiff( ...
                [2:2:length(rx_data_bin_depunc)], ...
                [4:6:length(rx_data_bin_depunc)] );
            rx_data_bin_depunc( B_idx ) = punctured_data( ...
                (N_HDR_CODED_END+2):2:length(punctured_data));

            depunctured_data = rx_data_bin_depunc;
end

Next, this is some of the code I am using to generate the test data:

% Generate test data
d=randint(1,90,[0 1]);
% Define trellis
t = poly2trellis( 7, [133 171] );
% Encode
d_enc=convenc(d,t);
% Puncture (using the above function)
[punc,depunc]=tmp_puncture(d_enc);
% Decode
y=vitdec(depunc,t,5,'cont','hard');
% Compare (noting additional trace-back delay in 'y')
biterr( d(1:85), y(6:90) )

ans =
       37


I would have hoped ans to be zero, but this is not the case.

Thanks for the help,

Stephen



Prasanna wrote:
> c...@hotmail.com wrote:
> > Steve,
> >
> > I'm sorry, i got confused with the input and output bits that you have
> > described.  If you have a rate k/n encoder, then for every n bits that
> > you input into the decoder, you should get k bits out.  That's all
>
> The other way around. Input bits are k, and output bits are n.
>
> > there is to it.  What type of decoding are you using with the function?
> >  DECTYPE=??  I'm pretty sure that it should be 'soft' for the Matlab
> > function (especially for punctured inputs) and then you need to specify
> > your number of quantisation bits.
> >
> > Hope that helps,
> >
> > col
> >
> >
> > Steve wrote:
> > > It's not really working, my BER is still very high.
> > >
> > > One thing that's bothering me is that by increasing the trace-back
> > > depth I lose more bits from the end of the bitstream. For example, say
> > > I have a 10 bit sequence and I have a trace-back depth of 5, then when
> > > I invoke the vitdec function in MATLAB, it returns a 10 bit vector (the
> > > first 5 bits are zero for the trace-back delay) and not 15 as I
> > > require. How can be obtain the final 5 bits of the sequence? Is it
> > > possible?
> > >
> > > Thanks,
> > >
> > > Stephen
> > >
> > >
> > > Phil wrote:
> > > > > >From what i remember the traceback length should be of the order of 5-6
> > > > > times the constraint length.  I would try that to start with; get the
> > > > > thing going and then work on shortening if required later on.
> > > >
> > > > Steve,
> > > >
> > > > I think the typical traceback length should be 5 time the constraint
> > > > length for a rate 1/2 code.  If you puncture your code, you are
> > > > weakening it.  For this reason, you will need to increase your
> > > > traceback length to make up for the weaker code.
> > > >
> > > > As suggested above, start at 5 or 6 times the constraint length.
> > > > However, instead of shortening it, I would lengthen it until you get
> > > > the BER you require.
> > > >
> > > > Let us know how it works out.
> > > >
> > > > Phil
>
> Hi Steve,
>
> You may have to call Matlab's vitdec function with the puncturing
> pattern as one of the parameters. If you already doing that, just cross
> check if you are passing the puncturing pattern in the same manner the
> vitdec function needs it to be.
>
> Also, if you can give  a few lines of code showing how you are using
> the convenc and vitdec, there are more chances you might get a useful
> answer.
> 
> Regards,
> Prasanna

Steve,

Don't take this the wrong way, but did you actually try any of the
suggestions posted earlier?  As far as i can see, from your code below,
you have constraint length = 7 and are using a traceback length of 5 in
the decoder!!  Combine that with the fact that the Matlab help file
tells you

      DECTYPE denotes how the bits are represented in CODE.  Choices
are:
       'unquant' : The decoder expects signed real input values.  +1
represents
                   a logical zero and -1 represents a logical one.
       'hard'    : The decoder expects binary input values.
       'soft'    : See the syntax below.

so when you specify 'hard' as the DECTYPE below, and then present the
decoder with binary data (punctured mind you) your expectation is that
the zeros that you have reinserted into the 'depunctured' BINARY
sequence will somehow yield a zero BER?

Sorry, perhaps i'm being rather flippant, but have you considered what
exactly is happening when you reinsert 'a value' into the coded
sequence at the input to the decoder?  You're basically telling the
decoder that those particular bits are equiprobable i.e. for a binary
sequence [0,1] you have to 'depuncture' with a value that is
equiprobable, 1/2 comes to mind.

col


Steve wrote:
> Hi,
>
> I'm using the student version of MATLAB, so it's not quite upto to date
> with respect to the commercial versions.
>
> I've looked over the VITDEC function documentation in my version of
> MATLAB and there is no reference to puncturing patterns, however in the
> on-line version of the documentation there is, which leads me to
> believe that this operation is not supported by my version of the
> software.
>
> Here is a copy of the code I am working with:
>
> First of all, there is a simple puncturing function that collects input
> binary data, punctures it and depunctures it. As far as I'm aware it is
> correct:
>
> function [ punctured_data, depunctured_data ] = tmp_puncture( data )
>
>     tx_bin_hdr_data = data;
>
>     N_HDR_CODED_END = 0;
>
>    % Allocate "Bit Stolen Data" vector
>             punc_vector_len = ...
>                 ( length(tx_bin_hdr_data) - N_HDR_CODED_END ) * (2/3);
>             tx_data_bin_punc = zeros(1, punc_vector_len);
>
>    % A
>             A_idx = setdiff( ...
>                 [(N_HDR_CODED_END + 1):2:length(tx_bin_hdr_data)], ...
>                 [(N_HDR_CODED_END + 5):6:length(tx_bin_hdr_data)] );
>             tx_data_bin_punc([1:2:length(tx_data_bin_punc)]) = ...
>                 tx_bin_hdr_data(A_idx);
>
>    % B
>             B_idx = setdiff( ...
>                 [(N_HDR_CODED_END + 2):2:length(tx_bin_hdr_data)], ...
>                 [(N_HDR_CODED_END + 4):6:length(tx_bin_hdr_data)] );
>             tx_data_bin_punc([2:2:length(tx_data_bin_punc)]) = ...
>                 tx_bin_hdr_data(B_idx);
>
>             punctured_data = tx_data_bin_punc;
>             % REMOVE PUNCTURING
>
>             punc_vector_len = ...
>                 ( length( punctured_data ) - N_HDR_CODED_END ) * (3/2);
>             rx_data_bin_depunc = zeros(1, punc_vector_len);
>
>             % A
>             A_idx = setdiff( ...
>                 [1:2:length(rx_data_bin_depunc)], ...
>                 [5:6:length(rx_data_bin_depunc)] );
>             rx_data_bin_depunc( A_idx ) = punctured_data( ...
>                 [(N_HDR_CODED_END+1):2:length(punctured_data)] );
>
>             % B
>             B_idx = setdiff( ...
>                 [2:2:length(rx_data_bin_depunc)], ...
>                 [4:6:length(rx_data_bin_depunc)] );
>             rx_data_bin_depunc( B_idx ) = punctured_data( ...
>                 (N_HDR_CODED_END+2):2:length(punctured_data));
>
>             depunctured_data = rx_data_bin_depunc;
> end
>
> Next, this is some of the code I am using to generate the test data:
>
> % Generate test data
> d=randint(1,90,[0 1]);
> % Define trellis
> t = poly2trellis( 7, [133 171] );
> % Encode
> d_enc=convenc(d,t);
> % Puncture (using the above function)
> [punc,depunc]=tmp_puncture(d_enc);
> % Decode
> y=vitdec(depunc,t,5,'cont','hard');
> % Compare (noting additional trace-back delay in 'y')
> biterr( d(1:85), y(6:90) )
>
> ans =
>        37
>
>
> I would have hoped ans to be zero, but this is not the case.
>
> Thanks for the help,
>
> Stephen
>
>
>
> Prasanna wrote:
> > c...@hotmail.com wrote:
> > > Steve,
> > >
> > > I'm sorry, i got confused with the input and output bits that you have
> > > described.  If you have a rate k/n encoder, then for every n bits that
> > > you input into the decoder, you should get k bits out.  That's all
> >
> > The other way around. Input bits are k, and output bits are n.
> >
> > > there is to it.  What type of decoding are you using with the function?
> > >  DECTYPE=??  I'm pretty sure that it should be 'soft' for the Matlab
> > > function (especially for punctured inputs) and then you need to specify
> > > your number of quantisation bits.
> > >
> > > Hope that helps,
> > >
> > > col
> > >
> > >
> > > Steve wrote:
> > > > It's not really working, my BER is still very high.
> > > >
> > > > One thing that's bothering me is that by increasing the trace-back
> > > > depth I lose more bits from the end of the bitstream. For example, say
> > > > I have a 10 bit sequence and I have a trace-back depth of 5, then when
> > > > I invoke the vitdec function in MATLAB, it returns a 10 bit vector (the
> > > > first 5 bits are zero for the trace-back delay) and not 15 as I
> > > > require. How can be obtain the final 5 bits of the sequence? Is it
> > > > possible?
> > > >
> > > > Thanks,
> > > >
> > > > Stephen
> > > >
> > > >
> > > > Phil wrote:
> > > > > > >From what i remember the traceback length should be of the order of 5-6
> > > > > > times the constraint length.  I would try that to start with; get the
> > > > > > thing going and then work on shortening if required later on.
> > > > >
> > > > > Steve,
> > > > >
> > > > > I think the typical traceback length should be 5 time the constraint
> > > > > length for a rate 1/2 code.  If you puncture your code, you are
> > > > > weakening it.  For this reason, you will need to increase your
> > > > > traceback length to make up for the weaker code.
> > > > >
> > > > > As suggested above, start at 5 or 6 times the constraint length.
> > > > > However, instead of shortening it, I would lengthen it until you get
> > > > > the BER you require.
> > > > >
> > > > > Let us know how it works out.
> > > > >
> > > > > Phil
> >
> > Hi Steve,
> >
> > You may have to call Matlab's vitdec function with the puncturing
> > pattern as one of the parameters. If you already doing that, just cross
> > check if you are passing the puncturing pattern in the same manner the
> > vitdec function needs it to be.
> >
> > Also, if you can give  a few lines of code showing how you are using
> > the convenc and vitdec, there are more chances you might get a useful
> > answer.
> > 
> > Regards,
> > Prasanna