Correcting Codes Are Used Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Error correcting codes are used for the reliable communication in noisy channel with less power consumption. In error correcting codes redundant bits are insert into the code word that we are transmitting so that receiver can correct the received code word if any error occurs during the transmission. There is various error correcting codes use according to the application.

In thesis we discuss Low Density Parity Check codes & its application in Digital Video Broadcasting Version 2 (DVB-S2). DVB-S2 is a Satellite broadband application. This system has been designed for the different application such as broadcasting, Internet access, for consumer application integrated receivers and decoder (IRD's) and personal computer, Internet trunking, data content distribution etc. In further chapter we discuss about DVB-S2 in detail.

In this chapter, I start with brief introduction of basic digital communication system and encoding and decoding scheme. Then brief description of error correcting codes and their applications in various communication systems. Then discuss about the Low Density Parity Check code which is used in Digital Video broadcasting version 2 (DVB-S2), their design architecture, their properties and application. Finally, in last chapter we discuss about the related works regarding design architecture of Low density parity Check code and its simulation result.

1.2 Digital Communication

Information Source

Source Encoder

Channel Encoder

Digital Modulator

Destination

Source Decoder

Channel Decoder

Digital Demodulator

Noise

Channel (wired or wireless)

Fig 1.1 Basic Block Diagram of Digital communication System

Figure 1.1 shows the basic block diagram of digital communication system [1]. The information source provide the message either in form of analog signal such as video or audio or in digital form such as data type. Next is the source encoder which can convert the information signal into a binary sequence. Then the channel encoder add some extra bits called redundant bits into the coded binary sequence that can overcome the noise effects at the time of transmission. Now the digital modulator modulates the binary sequence and converted into signal waveform. This signal transmitted through the physical medium called channel which may wire (cable) or wireless (air). At the time of transmission signal is corrupted due to unwanted signal called noise due to atmosphere, electronic device etc. At the receiving end corrupted signal is demodulated and converted into binary sequence. Then channel decoder reconstructs the original sequence by the knowledge of the code use at the transmission end. Now the source decoder retrieves the original message and sends it to destination.

1.3 Error Correcting Codes

In error correcting codes (ECC) extra bits called redundant bits are added in the encoded bits which are transmitting to permit the error detecting and correcting at the receiver end. These are use to correct the error due noise, fading, interference etc.

In 1948, Claude Shannon founded the noisy channel coding theorem in field of "Information Theory" [2]. In which he introduce that information can be quantified. He gives theorem called Shannon Theorem. The theorem states that for a Additive White Gaussian Noise (AWGN) channel of band width W channel capacity C is given by:

C = W log2 bits per second (1.1)

Where is the average signal energy and is the two sided noise power spectral density. The proof of this theorem is that if R is transmission rate and C is the channel capacity then transmission rate R less than or equal to channel capacity C, for error free transmission. If R is greater than C the probability of error is equal to unity.

Following table 1.1 shows the applications and required coding scheme according to that application:

Table 1.1 List of codes used in different area

Name of Code

Application

Wireless Communication Satellite Downlink

Convolution codes, turbo codes, LDPC

Tape recorder

Reed Solomon Code

Magnetic Discs

Hamming code

Computer Network

CRC

CD Player

Reed Solomon Code

1.4 Low Density Parity Check (LDPC) Codes

In 1962 LDPC codes are first proposed by R. Gallager. Due to high complexity LDPC codes are ignored in past years. Recent years because of excellent performance LDPC codes are widely consider in communication. LDPC codes are linear block codes defined by sparse parity check matrix. These codes are rediscovered by MacKay in 1999.

1.4.1 Fundamentals of Linear block codes

Linear block codes of (n, k) are completely defined by two matrixes called Generator Matrix G and Parity Check Matrix H where n is number codeword and k is number of message bits.

By Minimum hamming distance (dmin) determine the minimum correcting capacity of errors in the given code words

(dmin) is the minimum weight of Generator matrix's G row or minimum weight of parity matrix's H column.

For Example: Generator matrix and Parity check matrix of (7, 4) codes:

Generator matrix G = [Ik | P] k*n where P is parity matrix

n = 7 & k = 4

1 0 0 0 1 1 1

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 1

G =

H = [PT | In-k] (n-k)*n where PT is transpose of P

1 1 1 0 1 0 0

1 1 0 1 0 1 0

1 0 1 1 0 0 1

H =

1.4.2 Representation LDPC Codes

LDPC codes are represented by two methods first one is by the matrix representation same as all the linear block codes and second one is by the graphical representation. These are explaining as follows:

1.4.2.1 Matrix Representation

0 1 0 1 1 0 0 1

1 1 1 0 0 1 0 0

0 0 1 0 0 1 1 1

1 0 0 1 1 0 1 0

Let us take an example of LDPC code with the dimension of n x m (8, 4). The following equation 1.2 represents the parity check matrix:

H = (1.2)

In this matrix Wr & Wc are the No. of 1's in row and column respectively. For low density condition Wr << m & Wc << n.

1.4.2.2 Graphical Representation

For LDPC codes in 1981 Tanner introduce the graphical representation which is partially represent these codes and help to explain the decoding algorithm. Figure 1.2 represents the graphical representation of LDPC codes.

f0 f1 f2 f3

c0 c1 c2 c3 c4 c5 c6 c7

Fig: 1.2 Graphical representations of LDPC codes

In graphical representation there is m number of check nodes and there is n number of variable nodes. If element hij of matrix H is 1 then check node fi is connected to the variable node cj.

1.4.3 Regular & Irregular LDPC Codes

If Wc is constant for every column and Wc=Wr then LDPC code is regular LDPC code, otherwise code is irregular LDPC code.

Comparison between the error correcting codes shows in Table 1.2. Chung [3] showed that a rate ½ LDPC code with 107 AWGN channel which can achieve the Shannon limit 0.0045dB.

Table 1.2 Comparison of different channel codes Performance

Code type

Shannon Limit

LDPC

Turbo

Convolutional

Performance(dB)

Perror=10-6

Spars matrix H

Having Minimum number of 1's in rows and column

Minimum distance is expected large

Regular LDCP codes

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.