fec_conv

A Convolutional Encoding and Decoding

Copyright (c) March 2017, Mark Wickert All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of the FreeBSD Project.

sk_dsp_comm.fec_conv.binary(num, length=8)

Format an integer to binary without the leading ‘0b’

sk_dsp_comm.fec_conv.conv_Pb_bound(R, dfree, Ck, SNRdB, hard_soft, M=2)

Coded bit error probabilty

Convolution coding bit error probability upper bound according to Ziemer & Peterson 7-16, p. 507

Mark Wickert November 2014

Parameters:

R: Code rate

dfree: Free distance of the code

Ck: Weight coefficient

SNRdB: Signal to noise ratio in dB

hard_soft: 0 hard, 1 soft, 2 uncoded

M: M-ary

Notes

The code rate R is given by \(R_{s} = \frac{k}{n}\).

Examples

>>> import numpy as np
>>> from sk_dsp_comm import fec_conv as fec
>>> import matplotlib.pyplot as plt
>>> SNRdB = np.arange(2,12,.1)
>>> Pb = fec.conv_Pb_bound(1./2,10,[36, 0, 211, 0, 1404, 0, 11633],SNRdB,2)
>>> Pb_1_2 = fec.conv_Pb_bound(1./2,10,[36, 0, 211, 0, 1404, 0, 11633],SNRdB,1)
>>> Pb_3_4 = fec.conv_Pb_bound(3./4,4,[164, 0, 5200, 0, 151211, 0, 3988108],SNRdB,1)
>>> plt.semilogy(SNRdB,Pb)
>>> plt.semilogy(SNRdB,Pb_1_2)
>>> plt.semilogy(SNRdB,Pb_3_4)
>>> plt.axis([2,12,1e-7,1e0])
>>> plt.xlabel(r'$E_b/N_0$ (dB)')
>>> plt.ylabel(r'Symbol Error Probability')
>>> plt.legend(('Uncoded BPSK','R=1/2, K=7, Soft','R=3/4 (punc), K=7, Soft'),loc='best')
>>> plt.grid();
>>> plt.show()

(Source code)

class sk_dsp_comm.fec_conv.fec_conv(G=('111', '101'), Depth=10)

Class responsible for creating rate 1/2 convolutional code objects, and then encoding and decoding the user code set in polynomials of G. Key methods provided include conv_encoder(), viterbi_decoder(), puncture(), depuncture(), trellis_plot(), and traceback_plot().

Parameters:

G: A tuple of two binary strings corresponding to the encoder polynomials

Depth: The decision depth employed by the Viterbi decoder method

Examples

>>> from sk_dsp_comm import fec_conv
>>> cc1 = fec_conv.fec_conv(('101', '111'), Depth=10)  # decision depth is 10

Methods

bm_calc(ref_code_bits, rec_code_bits, …)	distance = bm_calc(ref_code_bits, rec_code_bits, metric_type)
conv_encoder(input, state)	output, state = conv_encoder(input,state)
depuncture(soft_bits[, puncture_pattern, …])	Apply de-puncturing to the soft bits coming from the channel.
puncture(code_bits[, puncture_pattern])	Apply puncturing to the serial bits produced by convolutionally encoding.
traceback_plot([fsize])	Plots a path of the possible last 4 states.
trellis_plot([fsize])	Plots a trellis diagram of the possible state transitions.
viterbi_decoder(x[, metric_type])	A method which performs Viterbi decoding of noisy bit stream, taking as input soft bit values centered on +/-1 and returning hard decision 0/1 bits.

bm_calc(ref_code_bits, rec_code_bits, metric_type)

distance = bm_calc(ref_code_bits, rec_code_bits, metric_type) Branch metrics calculation

Mark Wickert February 2014

conv_encoder(input, state)

output, state = conv_encoder(input,state) We assume a rate 1/2 encoder. Polys G1 and G2 are entered as binary strings, e.g, G1 = ‘111’ and G2 = ‘101’ for K = 3 G1 = ‘1011011’ and G2 = ‘1111001’ for K = 7 Input state as a binary string of length K-1, e.g., ‘00’ or ‘0000000’ e.g., state = ‘00’ for K = 3 e.g., state = ‘000000’ for K = 7 Mark Wickert February 2014

depuncture(soft_bits, puncture_pattern=('110', '101'), erase_value=3.5)

Apply de-puncturing to the soft bits coming from the channel. Erasure bits are inserted to return the soft bit values back to a form that can be Viterbi decoded.

Parameters:

• soft_bits –
• puncture_pattern –
• erase_value –

Returns:

Examples

This example uses the following puncture matrix:

\[\begin{split}\begin{align*} \mathbf{A} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \end{align*}\end{split}\]

The upper row operates on the outputs for the \(G_{1}\) polynomial and the lower row operates on the outputs of the \(G_{2}\) polynomial.

>>> import numpy as np
>>> from sk_dsp_comm.fec_conv import fec_conv
>>> cc = fec_conv(('101','111'))
>>> x = np.array([0, 0, 1, 1, 1, 0, 0, 0, 0, 0])
>>> state = '00'
>>> y, state = cc.conv_encoder(x, state)
>>> yp = cc.puncture(y, ('110','101'))
>>> cc.depuncture(yp, ('110', '101'), 1)
array([ 0., 0., 0., 1., 1., 1., 1., 0., 0., 1., 1., 0., 1., 1., 0., 1., 1., 0.]

puncture(code_bits, puncture_pattern=('110', '101'))

Apply puncturing to the serial bits produced by convolutionally encoding.

Parameters:

• code_bits –
• puncture_pattern –

Returns:

Examples

This example uses the following puncture matrix:

\[\begin{split}\begin{align*} \mathbf{A} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \end{align*}\end{split}\]

The upper row operates on the outputs for the \(G_{1}\) polynomial and the lower row operates on the outputs of the \(G_{2}\) polynomial.

>>> import numpy as np
>>> from sk_dsp_comm.fec_conv import fec_conv
>>> cc = fec_conv(('101','111'))
>>> x = np.array([0, 0, 1, 1, 1, 0, 0, 0, 0, 0])
>>> state = '00'
>>> y, state = cc.conv_encoder(x, state)
>>> cc.puncture(y, ('110','101'))
array([ 0.,  0.,  0.,  1.,  1.,  0.,  0.,  0.,  1.,  1.,  0.,  0.])

traceback_plot(fsize=(6, 4))

Plots a path of the possible last 4 states.

Parameters:

fsize : Plot size for matplotlib.

Examples

>>> import matplotlib.pyplot as plt
>>> from sk_dsp_comm.fec_conv import fec_conv
>>> from sk_dsp_comm import digitalcom as dc
>>> import numpy as np
>>> cc = fec_conv()
>>> x = np.random.randint(0,2,100)
>>> state = '00'
>>> y,state = cc.conv_encoder(x,state)
>>> # Add channel noise to bits translated to +1/-1
>>> yn = dc.cpx_AWGN(2*y-1,5,1) # SNR = 5 dB
>>> # Translate noisy +1/-1 bits to soft values on [0,7]
>>> yn = (yn.real+1)/2*7
>>> z = cc.viterbi_decoder(yn)
>>> cc.traceback_plot()
>>> plt.show()

(Source code)

trellis_plot(fsize=(6, 4))

Plots a trellis diagram of the possible state transitions.

Parameters:

fsize : Plot size for matplotlib.

Examples

>>> import matplotlib.pyplot as plt
>>> from sk_dsp_comm.fec_conv import fec_conv
>>> cc = fec_conv()
>>> cc.trellis_plot()
>>> plt.show()

(Source code)

viterbi_decoder(x, metric_type='three_bit')

A method which performs Viterbi decoding of noisy bit stream, taking as input soft bit values centered on +/-1 and returning hard decision 0/1 bits.

Parameters:

x: Received noisy bit values centered on +/-1 at one sample per bit

metric_type: Hard or soft decision decoding type. At present only 3-bit soft-decision is implemented.

Returns:

y: Decoded 0/1 bit stream

Examples

Take from fall 2016 final project

sk_dsp_comm.fec_conv.hard_Pk(k, R, SNR)

Calculates Pk as found in Ziemer & Peterson eq. 7-12, p.505

Mark Wickert November 2014

sk_dsp_comm.fec_conv.soft_Pk(k, R, SNR)

Calculates Pk as found in Ziemer & Peterson eq. 7-13, p.505

Mark Wickert November 2014

class sk_dsp_comm.fec_conv.trellis_branches(Ns)

A structure to hold the trellis states, bits, and input values for both ‘1’ and ‘0’ transitions. Ns is the number of states = \(2^{(K-1)}\).

class sk_dsp_comm.fec_conv.trellis_nodes(Ns)

A structure to hold the trellis from nodes and to nodes. Ns is the number of states = \(2^{(K-1)}\).

class sk_dsp_comm.fec_conv.trellis_paths(Ns, D)

A structure to hold the trellis paths in terms of traceback_states, cumulative_metrics, and traceback_bits. A full decision depth history of all this infomation is not essential, but does allow the graphical depiction created by the method traceback_plot(). Ns is the number of states = \(2^{(K-1)}\) and D is the decision depth. As a rule, D should be about 5 times K.