2022-01-22
Synchronization
Asynchronous and synchronous transmission Error detection/correction techniques
Line Configuration
Copyright By PowCoder代写 加微信 powcoder
2022-01-22
Digital Data/Digital Signals
SYNCHRONIZATION
sampling at the centre of each bit time
2022-01-22
Some encoding techniques
Bipolar-AMI Pseudoternary Manchester
Differential Manchester
SYNCHRONIZATION
• loss of synchronization
– In practice TB and TS are not equal. The result is that the timing of the receiver may slowly drift relative to the received signal.
2022-01-22
SYNCHRONIZATION
unpredictable time
SYNCHRONIZATION
• loss of synchronization
– Solution:
• data is sent in bit sequences called frames
• the receiving clock is started at the beginning of each bit sequence
– Question:
Since synchronization needs to be kept only for the duration of the frame, what is the length of the frame that will allow us to avoid loss of synchronization?
2022-01-22
ASYNCHRONOUS TRANSMISSION
• Timing or synchronization must only be maintained within each character; the receiver has the opportunity to resynchronize at the beginning of each new character.
idle state
unpredictable time
SYNCHRONIZATION
• loss of synchronization
– a frame consists of 11 bits
– assume that the synchronization at the start of the first bit is late at most 10% of TB
We must fulfill the following 2 conditions:
(1012)TS 0.1TB 11TB and (1012)TS 10TB
These are satisfied if: Ts TB 3.8% TB
2022-01-22
ASYNCHRONOUS TRANSMISSION
Timing requirements are modest. Sender and receiver are synchronized at the beginning of every character (8 bits if ASCII)
high overhead
overhead control_bits total _ bits
SYNCHRONOUS TRANSMISSION
In this mode, blocks of characters or bits are transmitted. Each block begins with a preamble and ends with a postamble
2 types:
character‐oriented bit‐oriented
2022-01-22
SYNCHRONOUS TRANSMISSION
Character‐oriented
the frame consists of a sequence of characters
one or more SYN characters
control control characters data characters
characters
SYN is a unique bit pattern that signals the receiver the beginning of a block
SYNCHRONOUS TRANSMISSION
character‐oriented ‐ 2 approaches
the receiver having detected the beginning of the block
reads the information till it finds the postamble
PREAMBLE POSTAMBLE
the receiver having received the preamble, looks for extra information regarding the length of the frame
starts to look
for next preamble
SYN SYN LEN
2022-01-22
SYNCHRONOUS TRANSMISSION
Bit oriented
In this mode, the frame is treated as a sequence of bits. Neither data nor control information is interpreted in units of x‐bit characters
a special bit pattern indicates the beginning of a frame
the receiver looks for the occurrence of the f lag
control fields
control fields
Dealing with presence of errors
• Detect presence of errors (error detection)
• Try to correct them (error correction)
• If no correction have the mechanism to request retransmission (use of Automatic Repeat Request)
2022-01-22
Random Errors
An error occurs when a bit is altered between transmission and reception
Random, statistically uniformly spread errors
occurrence of an error does not increase the probability that
other bits, close to the one in error, while be in error
white noise is producing such errors
For low BER and frames of “reasonable” length, most framers would experience no error or 1 error at most.
example: BER = 10^{‐6} and length of frame=[1000bytes*8=] 8,ooo bits
probability of receiving a frame correctly = [1‐10^{‐ 6}]^{8,000}>0.992
probability of a frame having a single error=8,000*receiving a frame correctly = 10^{‐6}*[1‐10^{‐6}]^{7,999}* {8,000}=0.007873
Probability of having more than 1 error<[ 1‐0.992‐ 0.007873=]0.000127
Burst Errors
Occurrence of an error having occurred in the sequence, means bits preceding/following the one in error have higher probability than the average bit error probability to be in error
Error strings (clusters of errored bits closely located in the sequence) form
Some channel related impairments producing error bursts
impulsive noise
“slow” fading/shadowing in wireless (relevance of bit rate to average time/distribution channel attenuation remains below certain level)
effect greater at higher data rates
2022-01-22
Error detection and control
detect and correct errors that occur in the transmission of frames
Types of errors
lost frame: a frame that the receiver does not receive (e.g., because starting of frame/clock extraction is not achieved due to excessive signal attenuation, increased levels of noise...)
damaged frame: a frame that the receiver receives, but some of its bits are in error
2022-01-22
Impact of error location
The frame consists of a sequence of characters
one or more SYN characters
control control characters data characters
characters
SYN is a unique bit pattern that signals the receiver the beginning of a block
Error Detection
2022-01-22
Error Correction/Detection Process
How Error Correction & Detection
Adds redundancy to transmitted message
Can deduce original despite some errors
Example: block error correction code
map k bit input onto an n bit codeword
each distinctly different
if get error assume codeword sent was closest to that received
means have reduced effective data rate
most of work concerning error correction & detection is making use of Galois field algebra (Boolean algebra ‐ mod_2 arithmetic – is a case of it)
2022-01-22
Code rate & minimum distance
Code rate r = # of information bits in a block k # of total bits in a block n
The bandwidth expansion is 1 / r = n / k
The energy per channel bit (Ec )is related to energy perinformationbit(Eb)throughEc rEb
Minimum distance (dmin ): Minimum number of positions in which any 2 codewords differ.
Correctable and detectable errors
A block code can correct at least errors if dmin > = 2 +1 => if dmin=3, then =1. If there is only one error in the block,
it can be corrected.
A block code can detect any error pattern if the received n bits
do not correspond to a codeword.
If there are errors in the n‐bits codeword, the existence of
errors is detected with certainly if < dmin.
However, even when >=dmin, many of the corrupted blocks
can still be detected.
Out of the 2n possible n‐bit combinations, only 2k codewords can be generated, thus, there are 2n ‐ 2k= 2k (2(n‐k)‐1) prohibited combinations.
Above statement applies when no error correction is used. 1-26
2022-01-22
A simple block code: (7,4) Hamming Code
0000 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
000 0000 110 1000 011 0100 101 1100 111 0010 001 1010 100 0110 010 1110 101 0001 011 1001 110 0101 000 1101 010 0011 100 1011 001 0111
•Error detection w/o error correction?
•Error detection with error correction?
•Minimum Humming distance? •Error Correction capability?
A simple block code: (7,4) Hamming Code
0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
011 0100 101 1100 111 0010 001 1010 100 0110 010 1110 101 0001 011 1001 110 0101 000 1101 010 0011 100 1011 001 0111 111 1111
•Error detection w/o error correction? 3
•Error detection with error correction? 0
•Minimum Humming distance? 3
•Error Correction capability? 1
2022-01-22
“Popular” Error Detection Techniques
Parity Checks
Longitudinal redundancy checks (LRC)
Cyclic redundancy checks (CRC)
Simple Error Detection Scheme
Parity check
Value of parity bit is such that character has even (even
parity) or odd (odd parity) number of ones Even number of bit errors goes undetected
2022-01-22
Parity Checks
Longitudinal Redundancy Checks
2022-01-22
Longitudinal Redundancy Checks
Longitudinal Redundancy Checks
2022-01-22
Longitudinal Redundancy Checks
Longitudinal Redundancy Checks
2022-01-22
Longitudinal Redundancy Checks
Cyclic Redundancy Check
Based on cyclic error‐correcting codes
For a block of k bits the transmitter generates n bit sequence
n insert redundancy in the codeword
Transmitter transmits the k+n bits
Receiver uses error detection process to decide if there were errors in the received sequence or otherwise
2022-01-22
Cyclic Codes
• “Cyclic code is a block code, where the circular shifts of each codeword gives another codeword that belongs to the code”.
• “They are error-correcting codes having algebraic properties that are convenient for efficient error correction & detection”.
Fundamentals of CRC coding
CRC codes treat bit strings as representations of polynomials with coefficients of 0 and 1 only (modulo 2 arithmetic)
11001↔1∗𝑋 1∗𝑋 0∗𝑋 0∗𝑋 1∗𝑋 𝑋 𝑋 1
Polynomial arithmetic is done modulo 2
subtraction and addition are similar to EXCLUSIVE OR
division is similar to the one in decimal except the subtraction is done modulo 2
Make sure you are familiar with mod2 arithmetic/algebra
2022-01-22
2022-01-22
CRC: Basic Idea
The sender and receiver agree upon “a generator polynomial”, G(x), in advance.
The sender appends a checksum (corresponds to the n redundancy bits) to the end of the (only data) frame, represented by the M(x) polynomial, in a way that the polynomial T(x), representing the {data + checksum bits} frame, is divisible by G(x).
Upon receipt of the frame, the receiver (generates and) divides H(x) by G(x) using modulo 2 division.
H(x) is the polynomial corresponding to the received sequence.
if there is a remainder, there has been transmission error. 1-43
How to compute the checksum
If n is the degree of G(x), then append n zero to the low order end of the frame; the resulting frame corresponds to the polynomial X n M (x).
DivideG(x)into XnM(x) usingmodulo2division.
11001↔1∗𝑋 1∗𝑋 0∗𝑋 0∗𝑋 1∗𝑋 𝑋 𝑋 1=M(X)
110010001∗𝑋 1∗𝑋 0∗𝑋 0∗𝑋 1∗𝑋 0∗𝑋 0∗𝑋 0∗𝑋 𝑋 𝑋 𝑋=𝑋 ∗𝑀𝑋
D(X): divisor; R(X): remainder
𝑋𝑀𝑋 𝐺𝑋𝐷𝑋𝑅𝑋
→𝐷 𝑋 ;𝑅𝑋
2022-01-22
How to compute the checksum
M(x) using modulo 2 subtraction/addition.
The result is the checksumed frame’s polynomial , T(x).
𝑇𝑥 𝑋𝑀𝑋𝑅𝑋
The frame corresponding to T(x) is transmitted.
T(X) XnM(X)R(x)[D(X)G(X)R(x)]R(X)
T ( X ) G(X) divides
T ( X ) D( X ) G( X ) O G( X ) D( X )perfectly T(X) (remainder = O)
CRC: an Example
• Frame: 1101011011
• Generator: 10011
2022-01-22
CRC Error Detection
Let us assume that some transmission errors occur Instead of receiving T(x), the receiver will receive
H(x)=T(x)E(x)
If there are k “1” bits in E(x), (it is most probable that) k
bit errors have occurred
the receiver computes (T(x) E(x))/G(x)=E(x)/G(x)
If G(x) contains two or more terms, (i.e. n>1) all single errorswill bedetected.
single‐bit error means E(X ) X m1, where 0 𝑚 𝑛 𝑘 1-47
Singleerrorand G(x)=Xn H(X)T(X)E(X) where
E(X ) O if no bit errors occur
E(X) X m1 if only the m-th bit of the [k+n]-bit long frame is reversed (0 𝑚 𝑛 𝑘; the larger the value of m is, the more significant the location of the bit within the frame is)
E(X) L(X)G(X) F(X)
H(X)T(X)E(X)T(X)L(X)G(X)F(X)
H ( X ) D( X ) L( X ) F ( X ) G(X) G(X)
Error will be detected if F(X ) O G(X)
For m-1>=n,L(X ) X mn1 and F(X ) O . Error is not detected. F(X) G(X)
For m-1