Linear Block Codes Mahdi Barhoush Mohammad Hanaysheh.

Презентация:



Advertisements
Похожие презентации
Convolutional Codes Mohammad Hanaysheh Mahdi Barhoush.
Advertisements

10.1 Chapter 10 Error Detection and Correction Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects.
HPC Pipelining Parallelism is achieved by starting to execute one instruction before the previous one is finished. The simplest kind overlaps the execution.
Michael Marchenko. In mathematics, a sequence is an ordered list of objects (or events). Like a set, it contains members (also called elements, or terms),
© The McGraw-Hill Companies, Inc., Chapter 4 Counting Techniques.
Ways to Check for Divisibility Vüsal Abbasov Dividing By 1 All numbers are divisible by 1.
S4-1 PAT328, Section 4, September 2004 Copyright 2004 MSC.Software Corporation SECTION 4 FIELD IMPORT AND EXPORT.
AVL-Trees COMP171 Fall AVL Trees / Slide 2 Balanced binary tree * The disadvantage of a binary search tree is that its height can be as large as.
© 2005 Cisco Systems, Inc. All rights reserved. BGP v Route Selection Using Policy Controls Applying Route-Maps as BGP Filters.
Combination. In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter.
Sequences Sequences are patterns. Each pattern or number in a sequence is called a term. The number at the start is called the first term. The term-to-term.
© 2005 Cisco Systems, Inc. All rights reserved. BGP v Customer-to-Provider Connectivity with BGP Connecting a Multihomed Customer to Multiple Service.
Multiples Michael Marchenko. Definition In mathematics, a multiple is the product of any quantity and an integer. in other words, for the quantities a.
Statistics Probability. Statistics is the study of the collection, organization, analysis, and interpretation of data.[1][2] It deals with all aspects.
1/27 Chapter 9: Template Functions And Template Classes.
7/29/2015Image Processing 1 Image Processing Using Matlab*
How can we measure distances in open space. Distances in open space.
Business Statistics 1-1 Chapter Two Describing Data: Frequency Distributions and Graphic Presentation GOALS When you have completed this chapter, you will.
TCP/IP Protocol Suite 1 Chapter 12 Upon completion you will be able to: Transmission Control Protocol Be able to name and understand the services offered.
Транксрипт:

Linear Block Codes Mahdi Barhoush Mohammad Hanaysheh

Introduction to Block Codes * Block codes introduce controlled amounts of redundancy into a transmitted data stream. * Block code systems divide uncoded data stream into fixed size blocks (k symbol), then add redundancy to each block (n-k symbols) to form the encoded data stream. * (k information symbol )+( n-k parity check symbol) >>> >>>> (n symbol code word) * Parity or redundancy bits are used for error detection and correction.

* Here, we have (n, k) code with rate R = k / n. * If the symbol is either 0 or 1 >>> Binary block code, symbols are named bits. * There are 2^n possible code words in a binary block code of length n. * From these, we choose 2^k code words to be mapped to M = 2^k different message. * Thus, a block of k information bits is mapped into a code word of length n selected from the set M = 2 ^ k code words. * Any code has a weight which is the number of nonzero elements that it contains.

* Hamming distance is the number of differences between the corresponding elements in any two code words. (measure of difference between any two code words) Ex. dh (1100,1111) = 2 dh (1100,1101) = 1 Then 1100 is closer to 1101 * The smallest hamming distance between any two code words is called the minimum hamming distance dh min. * The idea with error correction codes is to pick the 2^k code words of the 2^n total possible code words which are far enough apart (in terms of Hamming distance) to guarantee you are able to correct a certain number of errors. * dh min = 2*Ct + Dt +1

Linearity: * The block code is called linear block code if the addition of any two code words is also a code word. * The addition is performed under Galois Field GF(2) in binary block code. *Linearity implies that the linear block code must contain the all zeros code word.

How to generate a linear code ? Using linear algebra and matrices representation: C = m. G Where C is 1 X n code matrix. m is 1 X k message matrix. G is k X n Generation matrix of the code (The rows of the generator matrix are linearly independent and so G has a rank k. )

Ex. Let Find the code for m=[1001] Solution C = m. G = [1001]. G = [ ]

Linear systematic block code: In symmetric form, the code word C is compromised of a k information segment and a set of n-k symbols that are linear combination of certain information symbols determined by the P matrix. m = [m1 m2 m3 m4 ] >>> C = [C1 C2 C3 C4 C5 C6 C7] = [m1 m2 m3 m4 C5 C6 C7] Then, G = [ I k P] I k is the identity matrix P is k X (n - k) matrix

Parity check matrix H: The (n, k) linear code can be also specified by an (n –k) X n matrix H Such that any code C satisfies C. T(H) =[000…0]. The above formula implies that G. T(H) = 0 For systematic linear block code H= [ T(P) I n-k ]

Example.

Types of liner block codes: Hamming code. 1. Hamming code. Cyclic Codes. 2. Cyclic Codes. 3. Polynomial Codes. 4. Reed Solomon Codes. 5. Algebraic Geometric Codes. 6. Reed-Muller Codes. 7. Perfect Codes. 8. Repetition Codes.

Hamming code: * (n, k) = ( 2^w -1, 2^w -1- w), w is any positive integer let w =3 >>>> (7, 4) hamming code * In Hamming code, the parity check matrix H,the n column consists of all possible binary vectors except the all zero vectors. * dh min = 3 >>> can correct one error. * We have 2^k =16 codes such that C. T(H) = 0

Hamming code, single error correction: * Suppose that a single error occurred to the transmitted code C In the i th place, the received vector r = C + e(i) e(i) : zero row vector with length n except for the i th position. Using the barity check matrix H for decoding r. T(H) = ( C + e(i) ). T(H) = C. T(H) + e(i).T(H) = e(i). T(H) >>> Gives the location of the error