SÁCH SCAN - Mô hình hóa hệ thống và mô phỏng (GS.TS. Nguyễn Công Hiền TS. Nguyễn Phạm Thục Anh) unlocked
Preview textMỤC LỤC
LỜI NÓI ĐẦU.........................................................................Trong các hệ thống kỹ thuật số, dữ liệu được truyền cho giao tiếp có thể bị hỏng do nhiễu bên ngoài và bất kỳ lỗi vật lý nào khác. Nếu dữ liệu được truyền không khớp với dữ liệu đầu vào đã cho, thì nó được gọi là & 039;lỗi&039;. Việc truyền dữ liệu sẽ ở dạng bit (0 và 1) trong hệ thống kỹ thuật số. Nếu bit ‘1’ được thay đổi thành bit ‘0’ hoặc ngược lại, thì nó được gọi là lỗi bit. Các lỗi dữ liệu hay lỗi bit có thể xóa dữ liệu quan trọng trong hệ thống kỹ thuật số, trong nhiều trường hợp có thể gây hậu quả nghiêm trọng về thông tin. Có các loại lỗi khác nhau như lỗi bit đơn, nhiều lỗi và lỗi cụm. Trong đó, để giải quyết tình trạng này, chúng ta cần có các chương trình hoặc thuật giải mã hiệu quả. Một trong số những thuật giải mã đơn giản nhưng khá thông dụng hiện nay là mã Hamming; trong đó mã Hamming (7,4) là một dạng cơ bản, có thể truy vết và sửa chửa các lỗi bit đơn hiệu quả. Ngày nay, với việc áp dụng toán tin vào việc xử lí các vấn đề toán học nói chung đã trở nên đơn giản và phổ biến. Trong số các phần mềm xử lí số, MATLAB là một phần mềm được sử dụng phổ biến, có vai trò cung cấp môi trường tính toán số và lập trình, giúp xử lí các vấn đề toán học một cách dễ dàng hơn. Bài báo cáo của chúng em xin được trình bày phương pháp xử lí lỗi bit dữ liệu bằng mã Hamming (7,4) thông qua các cơ sở lí thuyết và việc tính toán bằng phần mềm Matlab. Trong quá trình thực hiện đề tài, do nhóm chúng em kiến thức còn hạn chế nên vẫn còn nhiều thiếu sót khi tìm hiểu, đánh giá, trình bày và thực hiện. Rất mong nhận được sự quan tâm, góp ý của các thầy / cô bộ môn để đề tài chúng em được đầy đủ và hoàn thiện hơn.PHẦN 2: NỘI DUNG
Bit dữ liệu (data-bit) là đơn vị thông tin cơ bản dùng để cung cấp thông tin trong máy tính, là một điểm dữ liệu được biểu diễn dưới dạng nhị phân (0 hoặc 1). Bit sửa lỗi/Bit chẵn lẻ (check-bit/ parity-bit) là một chuỗi bit được thêm vào các bit dữ liệu, sau đó đưa vào các chương trình sửa lỗi để kiểm tra phát hiện lỗi trong dữ liệu khi truyền đưa hoặc đọc/ghi trên phương tiện lưu trữ. Gọi M là các bit dữ liệu (data-bit), K là các bit kiểm tra (check-bit). Bit dữ liệu đầu vào (data in) sẽ được đưa qua một hàm kiểm tra để tìm lỗi, đồng thời cả hai bit đều được đưa vào bộ nhớ. Bit dữ liệu M1 sau khi đọc qua hàm f sẽ thu được bit M2 và K2, đồng thời đưa M2 qua hàm f tương tự thu được K3. Dữ liệu đầu vào Hàm kiểm tra (f) Bộ nhớ (Memory) Bộ so sánh (compare) kiểm tra (f) Hàm Bộ sửa chữa (corrector) M Dữ liệuđầu ra Báo lỗi K M2 K M1 K1 K Các trường hợp xảy ra: + K1, K2 và K3 đọc ra giống nhau => M1 và M2 giống nhau => M1 không bị lỗi => Xuất dữ liệu đầu ra (data out). + K1 giống K2 và khác K3 => M1 và M2 khác nhau => Dữ liệu lỗi, đưa vào bộ sửa chữa và xuất dữ liệu. + K1 giống K3 và khác K => Check bit bị sai, nhưng dữ liệu vẫn đúng nên vẫn xuất dữ liệu. + Trong trường hợp phát hiện 2 bit sai trở lên, bộ corrector không thể sửa được và báo lỗi (compare).
Khi đó G = 1 0 0 1 0 0 10 1 0 1 0 1 01 1 0 1 1 0 01 1 1 0 0 0 0Gọi E = {e 1 = (1;0;..;0); e 2 = (0;1;...;0);...; e 7 = (0;0;...;1)} là cơ sở chính tắc của Z 27 và {c 1 ;c 2 ;...;c 7 } là họ vectơ cột của H. Ta có các nhận xét: 1/ Hei = ci ≠ 0, i {1; 2; ...; 7} ( vì họ các vectơ cột của H khác không). 2/ Nếu v N(H) thì ( v ei )N(H) ( vì H(v+ei) = Hv + Hei = 0 + ci = ci ≠ 0 ). 3/ u là một vectơ của Z 2 thỏa Hu = ci => ( u ei )N(H) (vì H(u+ei) = Hu + Hei = ci + ci = 2ci = 0ci = 0) Ngoài ra j i, ( u ej )N(H).
Cho đoạn mã a gồm 4 data bit, a = {a 1 ; a 2 ; a 3 ; a 4 } Thực hiện phép toán v = aG để mã hóa a => v N(H) Vì cột 3, 5, 6, 7 của G là các vectơ đơn vị của cơ sở chính tắc của v R 4 => Các phần tử của v ở các vị trí đó sẽ tạo nên vectơ a, các vị trí còn lại đóng vai trò như những check bit. Sau đó gửi vectơ v cho người nhận, thu được vectơ w (có thể khác v do sai sót trong quá trình truyền dữ liệu). Nếu Hw = 0, tức w N(H) => Không có lỗi xảy ra,người nhận sẽ có được thông tin cần chuyển a tạo nên từ các phần tử ở vị trí 3, 5, 6, 7 của vectơ w. Nếu Hw ≠ 0 thì có lỗi xảy ra ở vị trí thứ i của w (w = v + ei). Khi đó Hw = Hv + Hei = 0 + Hei = ci. Dựa vào đây ta nhận biết lỗi nằm ở vị trí thứ i và sửa lỗi bằng cách đổi 0 <=> 1 tại vị trí i của w.
Hw = 1 0 0 = c 7. Suy ra lỗi xảy ra ở bit thứ 7 của w. Thay phần tử thứ 7 từ 1 thành 0 ta thu được vectơ giống v, sau đó rút các phần tử thứ 3,5,6,7 thu được data bit ban đầu là a. Lưu ý: Ta có thể xếp các phần tử khác 0 của Z 23 một cách tùy ý để tạo ra ma trận H. Tùy vào vị trí các cột vectơ đơn vị của R 4 trên G mà ta biết được vị trí của các phần tử vectơ a trong vectơ v = aG.
p1 p2 d3 p4 d5 d6 d PHẦN 3: CHƯƠNG TRÌNH MATLAB
Lệnh Tác dụng ~ Toán tử logic: không (not) clear Xóa biến khỏi bộ nhớ <Biến> = [A ; B ; C] trên mỗi hàng cách nhau bởi một dấu cáchLập ma trận có các hàng A,B, các phần tử eye(n) Tạo ma trận đơn vị cấp n mod ( số/ biến chia, số bị chia) Toán tử modulo (lấy phần dư) for <biến> = <gtrị đầu> : <mức tăng> : <gtrị cuối> Vòng lặp khi biết số lần lặp if...else.. Nếu..ì..ếu không thì... disp Hiển thị giá trị / chuỗi num2str Number to string - Chuyển dữ liệutừ kiểu số sang kiểu chuỗi
for ii = 1:n if ~find errvect = zeros(1,n); errvect(ii) = 1; search = mod(errvect * H& 039;,2); if search == syndrome find = 1; index = ii; end end end disp([&039;Position of error in codeword=&039;,num2str(index)]); correctedcode = recd; correctedcode(index) = mod(recd(index)+1,2) %Corrected codeword msg_decoded=correctedcode; msg_decoded=msg_decoded(1:4)
clear
correctedcode(index) =mod(recd(index)+1,2)
Chương trình nạp code Matlab Kết quả vận hành code PHẦN 4: KẾT QUẢ - KẾT LUẬN Nhóm đã hoàn thành việc tìm hiểu và thực hiện đề tài đã được đặt ra. Nhóm đã tiến hành tìm hiểu các vấn đề liên quan đến đề tài như: lỗi dữ liệu, lỗi bit, mã sửa lỗi - tập trung chủ yếu vào mã Hamming(7,4), cùng với cơ chế và cách vận hành thuật toán mã Hamming bằng ma trận. Xử lí được các số liệu và thuật toán bằng các công cụ Symbolic và công cụ giải số trong phần mềm lập trình Matlab. Kết quả vận hành thuật toán mà nhóm thu được đúng với mong muốn mà nhóm đặt ra. |