In the previous notebook we introduced the importance of channel coding and interleaving to combat inevitable bit errors during transmission. In this notebook, we will use the coding technique in a frame structure that lets the receiver know the meaning of each bit in the received bit stream.
The frame structure we design consists of a header with a known bit sequence and a payload block. At both the receiver and transmitter the structure and header information is known. On the other hand, the payload part contains the data we actually want to transmit so it is unknown at the receiver.
%load_ext autoreload
%autoreload 2
import numpy as np
import sys; sys.path.append('..')
try:
%load_ext tikzmagic
except ModuleNotFoundError:
print ("Did not find tikzmagic. You will not be able to compile the tex code!")
%matplotlib notebook
Pictorially, the frame structure is as follows, where we have L bits in the header and N bits in the payload.
# Source code has been redacted in online version
# Omitting 7 lines of source code
In our system, we implement a rudimentary physical (PHY, L1) and medium access control (MAC, L2) layer, see OSI model. The division of a system into different layers simplifies the system, as it distributes different responsibilities to different layers. For example, the PHY layer is responsible for packet detection and channel coding, whereas the MAC layer is responsible for error detection.
In our implementation, the PHY packet has a fixed size of $L+N$ bits, where $L$ is the number of header bits. The header is used for identification. The $N$ bits of the PHY payload are encoded bits describing one MAC frame. Pictorially, we can see it as follows:
%%tikz -l decorations.pathreplacing
\draw (0,0) rectangle +(3,0.8) node [midway] {MAC header};
\draw (3,0) rectangle +(2,0.8) node [midway] {App data};
\draw (5,0) rectangle +(2,0.8) node [midway] {Padding};
\draw (7,0) rectangle +(2,0.8) node [midway] {Checksum};
\draw [decorate,decoration={brace,amplitude=10pt}] (0,1) -- +(9,0) node [above,midway,yshift=10pt] {MAC frame};
The MAC frame is sent through the channel encoding to create the PHY payload. The elements of the MAC frame are as follows in our design:
Given these ideas, let us write a class that takes some application data and creates a packet from it. However, first we need two functions to convert decimal to binary and vice versa:
def int2bin(N, L):
result = []
for l in range(L):
result.append((N & 2**l) != 0)
return np.array(result[::-1]).astype(np.uint8)
print ("Conversion from decimal to binary:")
print ("==================================")
for i in range(16):
print ("%2d decimal = " %i, int2bin(i, 4), "binary")
def bin2int(bits):
result = 0
for i, b in enumerate(np.flipud(bits)):
result = result + b * 2**i
return result
print ("Conversion from binary to decimal:")
print ("==================================")
for b in ((0,0,0,0), (0,0,1,0), (0,0,1,1), (1,0,1,0), (1,1,1,1)):
b = np.array(b)
print ("%s binary = " % b, bin2int(b), " decimal")
Now, let's write a class from frame creation:
import crc8
import audioComms.channelcode as cc
class Packeting(object):
def __init__(self, headerBits, AppDataLength, useInterleaver=True):
"""headerBits contains the constant bits to identify the frame.
AppDataLength contains the maximum amount of data to fit into one frame"""
self._headerBits = headerBits.copy()
self._AppDataLength = AppDataLength
# the codewordLenght is the number of bits in the PHY payload
# given by codeRate * (MACframeLength)
# MACframeLength = 8bit length, AppDataLength, 8bit CRC
self._codewordLength = 3*(8 + self._AppDataLength + 8)
self._interleaver = np.arange(self._codewordLength)
if useInterleaver:
# Create Interleaver for the codewordlength
S = np.random.RandomState(seed=10)
S.shuffle(self._interleaver)
self._deinterleaver = np.argsort(self._interleaver)
# overall length of the PHY frame
self._packetLength = self._codewordLength + len(self._headerBits)
def createPacket(self, data):
"""Create a packet according to the given structure.
data contains the application data"""
L = len(data)
assert L <= self._AppDataLength # data in frame must be smaller than maximum length
lenBits = int2bin(L, 8)
paddingBits = np.zeros(self._AppDataLength - L)
# Build the PHY payload from length bits, data, padding and checksum
MAC_payload = np.hstack([lenBits, data, paddingBits]).astype(np.uint8)
hash = crc8.crc8()
hash.update(MAC_payload.astype(np.uint8).tobytes())
crcBits = int2bin(hash._sum, 8).astype(np.uint8)
PHY_payload = np.hstack([MAC_payload, crcBits]).astype(np.uint8)
# Apply rate 1/3 repetition channel code and create the overall packet
PHY_encoded = cc.repetition_encode(PHY_payload, 3)
PHY_encoded = PHY_encoded[self._interleaver]
return np.hstack([self._headerBits, PHY_encoded]).astype(np.uint8)
Let's try out this packet generator. For simplification, we do not use the interleaver, such that we can see the different parts in a better way. Moreover, the payload consists of [2,3,4,5], such that we can easily identify them in the stream:
# Create a generator with 4 bits header (1,1,1,1) and 4 bits application data
packeting = Packeting(headerBits=np.array([1,1,1,1]), AppDataLength=4, useInterleaver=False)
# Create a frame containing the data [0,0,0,0]
packet = packeting.createPacket(np.array([2,3,4,5]))
print (packet)
# The first 4 bits [1,1,1,1] correspond to the header:
print (packet[:4])
# The next 24 bits (3*8) correspond to a repetition-encoded length of the payload (which is 4 in our case):
print (packet[4:(4+3*8)].reshape((8,3)))
# The next 3*4 bits correspond to the actual payload
print (packet[(4+3*8):(4+3*8+3*4)].reshape((4,3)))
# The last 3*8 bit correspond to the CRC sum:
print (packet[-3*8:].reshape((8,3)))
Now, let's look at the structure, when we put less application data, e.g. only 3 bits into the frame:
packet = packeting.createPacket(np.array([2,3,4]))
print ("Header\n", packet[:4])
print ("Length (decimal 3)\n", packet[4:(4+3*8)].reshape((8,3)))
print ("Data\n", packet[(4+3*8):(4+3*8+3*4)].reshape((4,3)))
As we see, the length field encodes the number of actual payload bits (in this case 3). In addition, the payload is padded with zeros.
Now, that we have the packet generator defined, let's attempt to successfully decode a packet. In order to decode a packet, two criteria need to be fulfilled:
Let us implement both checks in the following decoder class:
class PacketingWithDecoder(Packeting):
def decodePacket(self, packet):
assert len(packet) == self._packetLength
# 1) Check if the header bits match exactly
if not np.all(self._headerBits == packet[:len(self._headerBits)]):
print ("Wrong header!")
return None
# extract the PHY payload and attempt decode it
PHY_encoded = packet[len(self._headerBits):]
PHY_encoded = PHY_encoded[self._deinterleaver]
PHY_payload = cc.repetition_decode(PHY_encoded, 3)
crcBits = PHY_payload[-8:]
MAC_payload = PHY_payload[:-8]
hash = crc8.crc8()
hash.update(MAC_payload.astype(np.uint8).tobytes())
# 2) Check the CRC checksum
if hash._sum != bin2int(crcBits):
print ("Wrong CRC")
return None
# Extract payload length and return the amount of payload
lenBits = MAC_payload[:8]
L = bin2int(lenBits)
return MAC_payload[8:(8+L)]
Now, we can evaluate if the decoder works. First, let's try to decode a packet with no bit errors:
packeting = PacketingWithDecoder(headerBits=np.array([1,1,1,1]), AppDataLength=4, useInterleaver=True)
payload = np.array([1,1,0])
packet = packeting.createPacket(payload)
decoded = packeting.decodePacket(packet)
print ("TX:", payload, "\nRX:", decoded, "\nSuccess: ", np.all(payload==decoded))
Fine, the decoder an decode a packet with no bit errors. It returns the correct payload.
Now, let's introduce some bit errors into the PHY payload part and try to decode:
# Source code has been redacted in online version
# Omitting 8 lines of source code
Great! The packet could still be decoded and we get the correct payload back.
Now, let's introduce more bit errors into the payload:
packet = packeting.createPacket(payload)
# introduce a burst of 10 bit errors
packet[8:18] ^= np.ones(10, dtype=np.uint8)
decoded = packeting.decodePacket(packet)
print ("TX:", payload, "\nRX:", decoded, "\nSuccess: ", decoded is not None and np.all(payload==decoded))
OK, now the packet cannot be decoded correctly. Too many bit errors occured within the frame. Hence, the repetition code could not correct all the bit errors. Therefore, the checksum was not correct and the application data could not be reliably extracted. We see the CRC fail from the output of the call.
Our packet decoder has one fundamental problem: If a bit error occurs within the PHY header, the decoder will not detect the packet at all, because the PHY header is not protected by a channel code. Let's illustrate this:
# Source code has been redacted in online version
# Omitting 8 lines of source code
Too bad, the packet decoded does not even try to decode the payload, because it could not verify that the packet is actually a frame based on the header. For simplicity, we will ignore this problem and provide a pragmatic solution in upcoming notebooks.
In this notebook, we have defined the frame structure we are going to use for our wireless transmission. The frame consists of a header for packet identification, a repetition-encoded payload and a checksum for checking successful decoding. In the upcoming notebook, we will put everything together to build a transmission chain that can actually transmit data.
Copyright (C) 2018 - dspillustrations.com