DOC PREVIEW
SBU CSE 590 - Coding and Applications in Sensor Networks

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Coding andCoding andAApplications in Sensor Networkspplications in Sensor NetworksJie GaoComputer Science DepartmentStony Brook UniversityPaperPaper• [Dimakis05] A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Ubiquitous Access to Distributed Data in Large-Scale Sensor Networks through Decentralized Erasure Codes, Symposium on Information Processing in Sensor Networks (IPSN'05), April, 2005.Why coding?Why coding?• Information compression• Robustness to errors (error correction codes)Source codingSource coding• Compression. • What is the minimum number of bits to represent certain information? What is a measure of information?• Entropy, Information theory.Channel codingChannel coding• Achieve fault tolerance.• Transmit information through a noisy channel.• Storage on a disk. Certain bits may be flipped. • Goal: recover the original information.• How? duplicate information.Source coding and Channel codingSource coding and Channel coding• Source coding and channel coding can be separated without hurting the performance.Source CodingChannelCoding01100011 0110Noisy ChannelDecode0110011100Decompress011001100011Coding in sensor networksCoding in sensor networks• Compression– Sensors generate too much data. – Nearby sensor readings are correlated.• Fault tolerance– Communication failures. Corrupted messages by a noisy channel.– Node failures – fault tolerance storage.– Adversary inject false information.ChannelsChannels• The media through which information is passed from a sender to a receiver.• Binary symmetric channel: each symbol is flipped with probability p.• Erasure channel: each symbol is replaced by a “?”with probability p.• We first focus on binary symmetric channel.Encoding and decodingEncoding and decoding• Encoding:• Input: a string of length k, “data”.• Output: a string of length n>k, “codeword”.• Decoding:• Input: some string of length n (might be corrupted).• Output: the original data of length k.Error detection and correctionError detection and correction• Error detection: detect whether a string is a valid codeword.• Error correction: correct it to a valid codeword.• Maximum likelihood Decoding: find the codeword that is “closest” in Hamming distance, I.e., with minimum # flips. • How to find it?• For small size code, store a codebook. Do table lookup.• NP-hard in general.Scheme 1: repetitionScheme 1: repetition• Simplest coding scheme one can come up with.• Input data: 0110010• Repeat each bit 11 times. • Now we have • 00000000000111111111111111111111100000000000000000000001111111111100000000000• Decoding: do majority vote. • Detection: when the 10 bits don’t agree with each other.• Correction: 5 bits of error.Scheme 2: ParityScheme 2: Parity--checkcheck• Add one bit to do parity check.• Sum up the number of “1”s in the string. If it is even, then set the parity check bit to 0; otherwise set the parity check bit to 1. • Eg. 001011010, 111011111.• Sum of 1’s in the codeword is even. • 1-bit parity check can detect 1-bit error. If one bit is flipped, then the sum of 1s is odd.• But can not detect 2 bits error, nor can correct 1-bit error.More on parityMore on parity--checkcheck• Encode a piece of data into codeword. • Not every string is a codeword. • After 1 bit parity check, only strings with even 1s are valid codeword.• Thus we can detect error.• Minimum Hamming distance between any two codewords is 2. • Suppose we make the min Hamming distance larger, then we can detect more errors and also correct errors.Scheme 3: Hamming codeScheme 3: Hamming code• Intuition: generalize the parity bit and organize them in a nice way so that we can detect and correct more errors. • Lower bound: If the minimum Hamming distance between two code words is k, then we can detect at most k-1 bits error and correct at most k/2 bits error. • Hamming code (7,4): adds three additional check bits to every four data bits of the message to correct any single-bit error, and detect all two-bit errors.Hamming code (7, 4)Hamming code (7, 4)• Coding: multiply the data with the encoding matrix.• Decoding: multiply the codeword with the decoding matrix.An example: encodingAn example: encoding• Input data: • Codeword:Original data is preservedSystematic code: the first k bits is the data.An example: decodingAn example: decoding• Decode: • Now suppose there is an error at the ith bit.• We received • Now decode:• This picks up the ith column of the decoding vector!An example: decodingAn example: decoding• Suppose• Decode:• Data more than 4 bits? Break it into chunks and encode each chunk. Second bit is wrong!Linear codeLinear code• Most common category.• Succinct specification, efficient encoding and error-detecting algorithms – simply matrix multiplication.• Code space: a linear space with dimension k.• By linear algebra, we find a set of basis • Code space:• Generator matrixLinear codeLinear code• Null space of dimension n-k: • Parity check matrix.• Error detection: check • Hamming code is a linear code on alphabet {0,1}. It corrects 1 bit and detects 2 bits error.Linear codeLinear code• A linear code is called systematic if the first k bits is the data.• Generation matrix G:• If n=2k and P is invertible, then the code is called invertible.• A message m maps to• Parity bits can be used to recover m. • Detect more errors? Bursty errors?Ik×k Pk×(n-k)m PmParity bitsReed Solomon codesReed Solomon codes• Most commonly used code, in CDs/DVDs.• Handles bursty errors.• Use a large alphabet and algebra.• Take an alphabet of size q>n and n distinct elements • Input message of length k: • Define the polynomial• The codeword isReed Solomon codesReed Solomon codes• Rephrase the encoding scheme.• Unknowns (variables): the message of length k• What we know: some equations on the unknowns.• Each of the coded bit gives a linear equation on the k unknowns.  A linear system.• How many equations do we need to solve it? • We only need length k coded information to solve all the unknowns.Reed Solomon codesReed Solomon codes• Write the linear system by matrix form:• This is the Van de Ment matrix. So it’s invertible.• This code can tolerate n-k errors.• Any k bits can recover the original message. • This property is called erasure code.2 10 11 1 12 11 22 2 22 11( )1( )1...


View Full Document

SBU CSE 590 - Coding and Applications in Sensor Networks

Download Coding and Applications in Sensor Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Coding and Applications in Sensor Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Coding and Applications in Sensor Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?