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