MÃ CHẬP LÝ THUYẾT THÔNG TIN

Bạn vẫn xem bản rút gọn của tài liệu. Coi và download ngay bạn dạng đầy đầy đủ của tài liệu tại trên đây (1007.31 KB, 13 trang )


Bạn đang xem: Mã chập lý thuyết thông tin

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNHVIỄN THÔNGBỘ MÔN: TRUYỀN DẪN SỐBÀI TIỂU LUẬN THEO NHÓMLớp D11VT2----------------------------Nhóm: 11CHỦ ĐỀ 11: MÃ CHẬP: BIỂU DIỄN MÃ CHẬP, GIẢI MÃ CHẬPĐề cương:Lời nói đầu.I.II.III.IV.Giới thiệu tầm thường về mã chập:1, reviews về mã chập và một trong những khái niệm.2, phương pháp tạo mã và một vài thông số quánh trưngBiểu diễn mã chập:1, màn biểu diễn thanh ghi dịch2, trình diễn theo sơ vật dụng lưới3, trình diễn theo sơ đồ câyGiải mã chập:
1, Giới thiệu cách thức giải mã Viterbi:2, Ưu điểm của cách thức giải mã:3, phương thức giải mã Viterbi:4, các bước giải mã:Phạm vi ứng dụng:LỜI NÓI ĐẦUTrong thời đại tin tức số hiên ni yêu cầu tin tức truyền đi cấp tốc chóngchính xác vị vậy mã chập được áp dụng để mã hóa thông tin đáp ứng yêu đó. Báo cáonhóm mình sẽ trình làng về mã chập ,cách tạo mã ,phương pháp biễu diễn mã chập vàphạm vi vận dụng của nó.Page 1I.Giới thiệu phổ biến về mã chập:1. Mã chập:Mã chập đươc elias đê cập đến đầu tiên nắm 1955. Tiếp đến wozencarft đưa ra một giảithuật giãi mã kha khá cho mã chập từ đó nghiên cứu và phân tích về mã chập càng ngày hoàn thiệnhơn. Năm 1965 massey gửi ra biện pháp giãi mã it công dụng nhưng dễ thực hiện hơn, được gọilà giãi mã ngưỡng. Nhờ hiện đại này mã chập được vận dụng để truyền số qua kênh thôngtin. Năm 1967, vertibi đã giới thiệu giãi thuật với phần lớn phiên bản sau của nó tạo cho mãchập được ứng dụng rộng thoải mái trong viễn thông.Mã chập (Convolution Codes) là một trong kỹ thuật mã hóa sửa không đúng (FEC). ConvolutinonCodes thuộc chúng ta mã lưới (mã hóa theo Trellis) và được xây dựng dựa vào một nhiều thứcsinh hoặc một sơ đồ gửi trạng thái (trellis mã) sệt trưng. Quy trình giải mã của mãchập phải dựa vào trellis mã trải qua các lời giải khác nhau, trong đó nổi giờ nhấtlà giải thuật Viterbi.
Mã chập là mã con đường tính gồm ma trận sinh có cấu trúc sao có thể chấp nhận được mã hóa rất có thể xemnhư một phép thanh lọc hoặc mang tổng chập. Mã chập được sử dụng thoáng rộng trong thực tế. Bởimã hóa được coi như như một tập hợp những bộ thanh lọc số đường tính với hàng mã là đầu ra output của cácbộ thanh lọc được ghép xen kẽ. Các mã chập là các mã đầu tiên được xây dựng các thuật toángiải mã quyết định phần mềm hiệu quả.-Ký hiêu mã chập (n,k,L) : k là đầu vàon là đầu raL bộ phận nhớ trong thanh ghi dịchSi(t)Nguồn tinLập mãchậpĐiều chếKênnh truyềnNguồn tinGiãi mã chậpGiãi điều chếSi(t)Page 2
Hình1.1 Sự bố trí bộ lập mã/giãi mã chập và cỗ điều chế / giãi pha trộn củamột con đường thông tin2. Bí quyết tạo mã và các đa thức đặc trưng:A. Bí quyết tạo mã-Thực hiện tại mã hóa dữ liệu một cách tiếp tục chứ không chia thành khối như mãkhối con đường tínhGiá trị những bit đầu vào là sự phối kết hợp của những bit đầu vào lúc này và những bit đầu vàotrước này đã lưu trong thanh ghihệ tất cả nhớSơ đồ chế tạo ra mã chậpmj………….mj-1-Lmj-Lbit tin tứcgL-1g0gL
+Đầu ra x jXj =mjg0 mj-1g1 …….. Mj-LgLtrong đó--gi là nhiều thức sinhxj phuc trực thuộc vào cực hiếm đầu vào bây giờ mj và L bit trước này đã lưu trong thanhghimỗi bit tin tức ảnh hưởng đến (L+1) bit cổng output khi nó được dịch trong thanh ghiB. Các thông số đặc trưng (n,k,K)n là số bít cổng output ở bộ lập mã khi đến k bit đông thời vào cỗ lập mãk là số đậy dịch vào bộ lập mã tại cùng 1 thời điểmPage 3K là độ dài tinh giảm thể hiện số lần dịch cực đại của 1 team k bản tin vào mànhóm k bit này vẫn còn gây ảnh hưởng tới đầu ra bộ lập mã- r=k/n là phần trăm mã (kkhối- Rc = k/n vận tốc mãIV.PHẠM VI ỨNG DỤNG- Mã chập được vận dụng trong truyền tin hiệu mặt hàng hải.- Tron INMARSAT C fan ta thực hiện mã chập để phát hiện và sữa lỗi
- Mã hóa chập với thuật giải mã Viterbi bây giờ được sử dụng khoảng chừng 4 tỷ năng lượng điện thoại(cellphones) sử dụng trên toàn gắng giới, rất có thể là lớn số 1 trong ngẫu nhiên ứng dụngnào. Tuy nhiên thì hiện tại thuật toán Viterbi được vận dụng nhiều độc nhất trong cácthiêt bị âm nhạc và hình hình ảnh kỹ thuật số. Một ước lượng ở Qualcomm mang đến thấyhiện nay thì khoảng chừng 1015 bits/s được giải thuật hóa do kỹ thuật Viterbi trongcác TV kỹ thuật số trên toàn cầm cố giới. Ngày nay, bọn chúng còn được thực hiện trongcác máy Bluetooth.-II. Trình diễn mã chập :Ngoài cách trình diễn theo sơ đồ cấu tạo hay ma trận tạo nên mã như nghỉ ngơi mục trước tacòn rất có thể biểu diễn theo 2 k(N - l) trạng thái của thanh ghi cùng sự chuyển trạng thái giữachúng khi tất cả k bit mới đi vào.1. Màn biểu diễn theo thanh ghi dịch:Bộ mã xoắn áp dụng thanh ghi dịch phụ thuộc vào trạng thái của thanh ghi dịch, với đathức tạo mã lối ra của thanh ghi dịch để được tài liệu lối ra lúc lối vào là một trong những bit tốt 1nhóm bit lối vào dựa vào bộ tạo nên mã2. Màn biểu diễn theo sơ đồ vật lưới:Page 4Bộ mã xoắn sử dụng sơ trang bị lưới sẽ phụ thuộc vào vào đôi mắt lưới trước kia và đường đi củamắt lưới tiếp theo làm cho ta bit lối ra. Phụ thuộc vào số đậy lối ra khác nhau mà sốmắt lưới khớp ứng ở cột lưới có thể có là 2 k đôi mắt lướiSơ đố lưới với một bit lối vào và 2 bit lối ra.Bộ mã lưới lối vào bit 0 tương xứng với đường nét liền và lối vào bit 1 tương ứngvới con đường nét đứt.Xét bộ mã xoắn cùng với sơ thiết bị lưới cùng với k = 1, n = 2 cùng N = 3

Xem thêm: Hướng Dẫn Cấu Hình Router Trên Packet Tracer, Tự Học Ccna Lab 1: Cấu Hình Router Cisco Cơ Bản

Số tinh thần của thanh ghi là 2 k(N - ^ = 22 = 4 có nghĩa là tương ứng với 00, 01, 10, 11.Trong sơ trang bị lưới những trục ngang trình diễn sự thay đổi của trạng thái có thể của k(N - 1)bit bên trên thanh ghi. Những bit nhị phân viết cạnh mũi tên nối 2 trạng thái tiếp liền theo thờigian biểu lộ lối ra của bộ mã hóa trước thời điểm chuyển này. Từng một lần mã hóa mộtcụm dữ liệu ta luôn luôn suất phân phát từ tâm trạng toàn 0 ban đầu đi theo một mặt đường qua sơ đồlưới rồi lại chấm dứt ở tâm trạng toàn 0.3. Màn trình diễn theo sơ đồ gia dụng cây:Page 5Ví dụ: cỗ mã hoá v1 = r1, v2 = r1 + r2 + r 3, v3 = r1 + r3 biểu đạt vào được biểuthị theo cây mãChuỗi 4 bit vào 1011 được mã hoá thành 111 010 100 101( tốc độ mã là 1/3).Quan gần kề sơ đồ ta thấy sự lặp lại kết cấu khi số tầng to hơn độ dài ràng buộc vủa nóvà tất cả các nhánh xuất phất tự 2 nốt cùng trạng thái sẽ đến m các dãy tương đương nhau.Điều này có nghĩa là 2 nốt cùng tên hoàn toàn có thể nhập làm cho một.Bằng biện pháp này ta có thể rút gọn gàng sơ đồ dùng cây thành sơ vật dụng lưới màn trình diễn mã xoắn gọn hơn.Hàm truyền cho tin tức về các đường không giống nhay vào sơ thứ lưới tự trạng tháitoàn o bân đầu trở về tinh thần toàn o lần vật dụng nhất. Hàm truyền nhập vai trò quan trọngtrong việc nhận xét giới hạn xác suất lỗi của mã. Khớp ứng với từng nhánh nối 2 trạngthái là hàm dạng DaNb J7 được định nghĩa, ở kia a là số bit một trong dãy bit ra cùng b là số bit 1trong hàng bit vào tương ứng của nhánh cùng 7 là số nhánh trong mặt đường đi. Hàm truyền củamã còn được gọi là hàm truyền của lối đi từ tinh thần toàn o cho trạng thái toàn o kế tiếpPage 6kí hiệu là T(D, N, J), từng số hạng của T(D, N, J) là một trong đường trong sơ thiết bị lưới đi từ bỏ bắtđầu toàn 0 đến ngừng toàn 0.
Từ biểu thức trên ta hoàn toàn có thể thấy vĩnh cửu một từ bỏ mã tất cả trọng lượng Hamminh 5, 2 từmã trọng lượng Hamminh 6. Ở từ mã tất cả trọng lượng Hamming 5 tương ứng với hàng vàotrọng lượng Hamming 1 độ lâu năm 3. Số mũ nhỏ tuổi nhất của D trong triển khai T(D, N, J) gọi làkhoảng cách tự do của mã xoắn ký hiệu là dfree trong lấy ví dụ trên dfree = 5.III. Giải mã chập (theo thuật toán Viterbi):1. Giới thiệu cách thức giải mã Viterbi:Năm 1967 Viterbi chuyển ra phương pháp giải mã chập là loại trừ các băng thông ítgiống nhau duy nhất hay nói một cách khác là chọn ra từ mã gồm số đo kỹ năng giống nhaucực đại (Maximum Likehood neetvic). Phương pháp giải mã này được gọi là thuật toánVicterbi. Thuật toán này được sử dụng thoáng rộng cho việc giải mã chập.Nếu toàn bộ các chuỗi vào đều có xác suất tương đồng thì cỗ giãi mã giành được xác suấtlỗi tốt nhất đã là cỗ giải mã thực hiện so sánh các tỷ lệ có điều kiện được điện thoại tư vấn là cáchàm có công dụng giống nhau. (Likehood Funtion) phường (Z/) và chọn ra giá trị rất đại. Bộgiải mã lựa chọn nếu:P (Z/) = Max phường (Z/)Các hàm hợp lý và phải chăng thường mang lại sẵn hay dựa vào các công năng kênh truyền.2. Ưu, điểm yếu kém của phương thức giải mã:- Ưu điểm của phương pháp giải mã này đối với các phương pháp khác là độ phứctạp của lời giải không tang lúc số che trong chuỗi trường đoản cú mã tang. Thuật toán tổng quan việctính toán số đo kiểu như nhau hay khoảng cách giữa biểu đạt thu được tại thời gian vàđường dẫn của lưới đi mang lại mỗi tâm trạng tại thời gian này.Page 7Thuật toán giải mã cho phép loại bỏ bài toán xem xét những đường dẫn không tồn tại khảnăng ứng cử cho câu hỏi lựa chọn. Khi hai tuyến phố dẫn đi vào cùng một trạng thái, thì đườngdẫn nào bao gồm số đo rất tốt sẽ được lựa chọn; đường dẫn này được call là đường truyền sống
sót “surviving”. Việc quyết định những đường dẫn sống sót được triển khai ở các trạng thái.Bộ giải mã thường xuyên như vậy nhằm tiến sâu vào lưới cùng với việc quyết định thải trừ cácđường dẫn ít kiểu như nhau nhất. Như vậy mục đích của vấn đề chọn xuống đường dẫn về tối ưu làchọn lựa trường đoản cú mã gồm số đo kĩ năng giống nhau cực đại (Maximum Likehôd Melvic) haynói một bí quyết khác là lựa chọn ra một tự mã có số đo giỏi nhất. Thủ tục giải thuật thường gọi làthuật toán vì trước đây nó thường được thực hiện ở đoạn mềm trên máy tính xách tay hay ở bộ vixử lý, nhưng bây giờ để tăng tốc độ xử lý nó được triển khai ở các vi mạch khuôn khổ lớn.- Nhược điểm: việc mã hóa và giải thuật lien quan đến mã chập chỉ xử lý đượccác lỗi 1 bit còn đối với các kênh truyền xuất hiện nhiều bit lien tiếp thì thuật toán mã hóavà giải mã này sẽ không còn tuyệt đối nữa.Kênh truyền ở chỗ này phải là kênh truyền ít nhiễu, vày nếu kênh truyền nhiễu thừa lớn,mã hóa chập sẽ không còn còn tốt nữa.3. Phương pháp giải mã Viterbi:Xác định tài liệu dựa trên khẳng định đường mã buổi tối ưu.Xác định đường mã được chọn bằng đưởng mã gồm chỉ số đo nhỏ nhất.Chỉ số đo của đường mã bằng tổng chỉ số đo của những nhánh thuộc con đường mã.Chỉ số đo của từng nhánh bằng khoảng cách Hamming giữa áp sạc ra trong sơ đồlưới mã với dữ liệu thu tương ứng.4. Các bước giải mã chập:Ví dụ: Xét quá trình giải mã Viterbi đến mã tích chập (2, 1, 2): g(1) = (1, 1, 1)Page 8 g(2) = (1, 0, 1)Phía phát yêu cầu truyền bạn dạng tin bao gồm 12 bits.Chuỗi dữ liệu thu được ở phía thu bao gồm 24 bits như sau:Y = 110111000110001111101100Ta có quá trình giải mã như sau:Bước 1: desgin lưới mã theo thời gian như sau:
Page 9Bước 2: bước đầu từ tinh thần a (có giá trị chạy (running metric) bởi 0) lần lượt tính chỉsố đo (metric) của những nhánh rất có thể dựa vào dữ liệu thu và sơ trang bị lưới mã.Bước 3: Tính chỉ số đo của từng nhánh nhờ vào khoảng phương pháp Hamming.Bước 4: Tính quý hiếm chạy của mỗi node bằng cách cộng cực hiếm chạy của node trước đóvới chỉ số đo của nhánh gửi trạng thái thân hai node này:Bước 5: lặp lại quá trình giám sát và đo lường cho tất cả các đưa trạng thái có thể có tại các node:Page 10Bước 6: lặp lại quá trình đo lường và thống kê như phần trước.Bước 7: Khi có nhánh mang lại cùng 1 node, nhánh nào tạo nên giá trị chạy tại node đó khủng hơnnhánh kia sẽ bị loại bỏ bỏ:Bước 8: quy trình được lặp lai cho đến khi không còn dữ liệu.Bước 9: trường đoản cú trạng thái cuối cùng (trạng thái a), đi ngược lại (từ đề xuất sang trái) nhằm xác địnhđường mã còn trường tồn => đấy là đường mã tối ưu.Bước 10: Từ con đường mã buổi tối ưu, ta khẳng định được tài liệu thu. Theo công việc trên lấy ví dụ 1 đã thu được sơ đồ tương đối đầy đủ như sau:Page 11Chuỗi dữ liệu thu được là: 110111001000
Page 12TÀI LIỆU THAM KHẢO:1. Giáo trình: “truyền dẫn số” - học viện technology bưu chính viễn thông2. Digital Communications by John Proakis3. Slide bài giảng môn “Truyền dẫn số”LỜI KẾTMã chập nguyên lý tạo ,giải mã và áp dụng là đề tài mang ý nghĩa chất nghiên cứulý thuyết mã hoá biểu đạt và các quá trình xẩy ra trong các số đó . Thực hiện quá trình này giúpphân tích với các ví dụ khá cụ thể các qúa trình sử lý của các phương thức mã hoá.Với thời gian và kỹ năng và kiến thức có hạn trong bài làm của tập thể nhóm chắc ko tránh khỏinhững thiếu hụt sót, hạn chế. Vày vậy chúng em rất ước ao được những thầy đóng góp ý kiến bổxung để bài xích làm của chúng em được đầy đủ và hoàn thiện hơn.Em xin cảm ơn!Page 13


*
biểu diễn ma trận 5 784 5
*
trình diễn tính bình ổn mũ của họ tiến hóa dưới dạng gật đầu được của không khí orlicz 38 398 0