TAILIEUCHUNG - Illustration of the TSP algorithm

Convolutional codes are linear. Therefore, the Hamming distance between any pair of code sequences corresponds to the Hamming distance between the allzero code sequence and some nonzero code sequence. The nonzero sequence of minimum Hamming weight diverges from the allzero path at some point and remerges with the allzero path at some later point | Illustration of the TSP algorithm st 1 st 2 IEM UNI st 3 st 4 survivor Key idea Best path from A to C = best of - the path A-F-C - best path A to B + best path from B to C - the path via D does not influence the best way from B to C A B C D E F Viterbi algorithm the Viterbi algorithm is a standard component of tens of millions of high-speed modems. It is a key building block of modern information infrastructure The symbol "VA" is ubiquitous in the block diagrams of modern receivers. Essentially: the VA finds a path through any Markov graph, which is a sequence of states governed by a Markov chain. many practical applications: convolutional decoding and channel trellis decoding. fading communication channels, partial response channels in recording systems, optical character recognition, voice recognition. DNA sequence analysis etc. Application to convolutional code encoder VD channel Info code code + noise estimate binary noise sequences P(n1=1)=P(n2=1) = p I delay c1 c2 n1 n2 c1 n1 c2 n2 VITERBI DECODER: find sequence I‘ that corresponds to code sequence ( c1, c2 ) at minimum distance from (r1,r2) = (c1 n1, c2 n2) Use encoder state space (Trellis Diagram) I delay c2 00 01 11 10 State 0 State 1 Time 0 1 2 3 00 01 11 10 00 01 11 10 00 01 11 10 ••• 00 11 State 0 State 1 00 01 11 10 00 01 11 10 00 01 11 10 ••• 00 11 State 0 State 1 00 01 11 10 00 01 11 10 00 01 11 10 ••• Encoder output 00 11 10 00 channel output 00 10 10 00 0 2 1 1 1 2 1 3 best Viterbi Decoder action VITERBI DECODER: find sequence I‘ that corresponds to code sequence ( c1, c2 ) at minimum distance from ( r1, r2 ) = ( c1 n1, c2 n2 ) Maximum Likelihood receiver: find ( c1, c2 ) that maximizes Probability ( r1, r2

• Kĩ thuật Viễn thông
• Giáo trình Lý thuyết thông tin
• Độ do lượng tin
• Sinh mã tách được
• Kênh truyền tin rời rạc
• Sửa lỗi trên kênh truyền
• hệ thống thông tin
• bài giảng Lý thuyết thông tin
• tài liệu Lý thuyết thông tin
• đề cương Lý thuyết thông tin
• bài tập Lý thuyết thông tin
• lý thuyết thông tin
• kênh thông tin rời rạc không nhớ
• sửa lỗi kênh truyền
• tài liệu học đại học
• bài giảng về lý thuyết thông tin
• kỹ thuật thông tin liên lạc
• bài giảng về công nghệ viễn thông
• Khoa học máy tính
• Giáo trình môn học Lý thuyết thông tin
• Độ đo thông tin
• Đồ họa máy tính
• Lý thuyết số
• Giáo trình lý thuyết
• bài giảng lý thuyết
• lý thuyết hệ thống
• thông tin liên lạc
• Mô hình lý thuyết thông tin
• Độ đo lượng tin
• Định lý cơ sở của kỹ thuật truyền tin
• Dung lượng kênh truyền
• Kênh truyền tin rời rạc không nhớ
• Cơ sở lý thuyết truyền tin
• Hệ thống truyền tin
• Mã hóa thông tin
• Điều chế thông tin
• Khái niệm mã hóa