khái niệm cơ bản
Tín hiệu - tin tức
Hình 1.1: Sơ đồ hệ thống thông tin
Tín hiệu là một thuật ngữ dùng để chỉ những vật thể, dấu hiệu, phần tử ngôn ngữ hoặc biểu tượng đã được công nhận, nhằm truyền tải thông tin Nói cách khác, tín hiệu chính là biểu hiện vật lý của thông tin cần được chuyển từ nguồn đến người nhận.
Tin tức là những thông tin quan trọng được truyền tải từ nguồn đến người nhận, bao gồm tiếng nói, âm nhạc, hình ảnh và số liệu Đặc điểm nổi bật của tin tức là tính bất ngờ, vì người nhận thường không biết trước nội dung sẽ được thông báo.
Tín hiệu: Tín hiệu là biểu hiện vật lý của tin tức mà nó mang từ nguồn tin đến nơi nhận tin.
Hệ thống bao gồm các thiết bị phần cứng và thuật toán phần mềm, thực hiện các tác động theo quy tắc nhất định lên tín hiệu đầu vào, nhằm tạo ra tín hiệu đầu ra khác Đây là những khái niệm và vấn đề quan trọng trong lý thuyết tín hiệu.
Phân loại tín hiệu
2.1 Dựa trên quá trình biến thiên
Tín hiệu xác định: là tín hiệu mà quá trình biến thiên hoàn toàn xác định, được biểu diễn bằng một hàm thực hoặc phức theo thời gian
6 x(t) = e - t với t >0, >0 y(t) = (1- e - t ) với t >0, >0 Tín hiệu ngẫu nhiên: là tín hiệu mà quá trình biến thiên không được báo trước, muốn biểu diễn phải tiến hành quan sát thống kê.
Tín hiệu năng lượng: x(t) 0 khi t
Tín hiệu năng lượng là tín hiệu có: 0 < Ex <
Tín hiệu công suất: x(t) const khi t
Tín hiệu công suất là tín hiệu có: 0 < Px <
- Tín hiệu tương tự: Tín hiệu có thời gian và biên độ liên tục (analog). x(t) t
- Tín hiệu rời rạc: Tín hiệu có biên độ liên tục – thời gian rời rạc. x(t) t
- Tín hiệu lượng tử: Tín hiệu có biên độ rời rạc - thời gian liên tục. x(t)
- Tín hiệu số: Tín hiệu có biên độ và thời gian đều rời rạc (digital).
Biểu diễn gỉai tích tín hiệu
Việc lựa chọn mô hình toán học phù hợp là rất quan trọng trong phân tích và xử lý tín hiệu Mô hình này cần đáp ứng các yêu cầu cụ thể để đảm bảo tính chính xác và hiệu quả trong quá trình xử lý.
- Dễ dàng cho việc tính toán và đo lường các thông số của tín hiệu.
- Biểu diễn chính xác các tính chất vật lý của tín hiệu.
Thông thường có hai cách biểu diễn tín hiệu là biểu diễn rời rạc và biểu diễn liên tục được trình bày sau đây.
3.1 Biểu diễn liên tục tín hiệu
Biểu diễn tín hiệu có thể thực hiện thông qua các hàm thực hoặc phức, dựa trên các biến thực hoặc phức Trong thực tế, hình thức biểu diễn liên tục phổ biến nhất thường là các biến đổi tích phân.
X(s) = ∫ x ( t ) φ ( t x, xs ) dt x,t ∈ xτ x(t) =∫ X ( s ) ɸ ( s, xt ) ds, xs ∈Ω τ Ω φ (t x,s) : nhân xliê xnhợ xp ɸ ( s,t) : nhânbi xế xnđổ xi
Tuỳ theo việc chọn nhân biến đổi, ta có các biến đổi liên tục khác nhau: Biến đổi Laplace, Biến đổi Fourier, Biến ổi Hillbert a Biến đối Laplace:
Biến đổi Laplace được ứng dụng để phân tích quá độ. b Biến đổi Fourier:
3.2 Biểu diễn rời rạc tín hiệu
Là khai triển tín hiệu thành tổ hợp liên tục bởi các hàm x i (t); n
X(t) = ∑ a i xx i ( t ) là biểu thức mô tả tín hiệu x(t) trong không gian a, trong đó { x i (t)} là tập hợp các hàm cơ sở Các hệ số { α i } biểu diễn tín hiệu x(t) thông qua chuỗi lưỡng giác Fourier, cho phép phân tích tín hiệu không tuần hoàn bằng các hàm điều hòa thực.
) a 0 = 1 ∫ T xx ( t ) dt x, [0 ,T ] làthời xhạn xcủatínhiệu xx (t) xT 0
T 0 T 0 b Tập hàm điều hoà phức ( chuỗi phức Fourier).
∞ 2 π x(t) = ∑ X n xe x jωtn xωt 0 t x,ωt 0 = ,T xlàthời xhạn xcủax (t ) n=−∞ T
T : là xchukhỳ xtínhiệu x, xt 0 làmột xđiểmbất xkỳ ∈ (−∞ x,∞ ).
hiệu xác định
Các thông số của tín hiệu xác định
Tích phân tín hiệu đại diện cho diện tích dưới đồ thị của tín hiệu, và thông số này có thể khác nhau tùy thuộc vào loại tín hiệu.
Với tín hiệu tồn tại trong khoảng thời gian hữu hạn ( t 1, t 2), tích phân tín hiệu được xác định như sau: t 2
Với tín hiệu tồn tại vô hạn (- ∞ x,+∞ ¿:
Thời gian tồn tại của tín hiệu, hay còn gọi là thời hạn của nó, là một khái niệm quan trọng trong lĩnh vực tín hiệu Các tín hiệu có thời hạn hữu hạn thường phản ánh chính xác các mô hình thực tế của tín hiệu vật lý.
2.1.2 Giá trị trung bình của tín hiệu
Với tín hiệu thời hạn hữu hạn: t 2
Với các tín hiệu có thời hạn vô hạn:
Tín hiệu tuần hoàn là loại tín hiệu có thời gian vô hạn, nhưng giá trị của nó lặp lại sau mỗi chu kỳ Do đó, trị trung bình của tín hiệu này được xác định trong một chu kỳ, từ t 0 đến t 0 + T.
2.1.3 Năng lượng của tín hiệu.
Năng lượng tín hiệu được định nghĩa bởi tích phân của bình phương tín hiệu:
Với tín hiệu có thời hạn hữu hạn t 2
Và tín hiệu có thời hạn vô hạn
Từ thông số năng lượng, người ta đưa ra định nghĩa về tín hiệu năng lượng như sau: tín hiệu năng lượng hữu hạn là tín hiệu có 0 < E x < ∞
Tín hiệu năng lượng là loại tín hiệu có thời gian tồn tại hữu hạn, trong khi tín hiệu quá độ là những tín hiệu có giá trị giảm dần về 0 khi thời gian tiến tới vô cùng (t → ∞).
2.1.4 Công suất trung bình của tín hiệu.
Công suất trung bình của tín hiệu theo định nghĩa là tỉ số giữa năng lượng và thời hạn của tín hiệu được ký hiệu là P x
Với tín hiệu có thời hạn hữu hạn: t
Với các tín hiệu có thời hạn vô hạn:
Công suất trung bình của tín hiệu tuần hoàn được xác định trong một chu kỳ: t 0 +T
Tín hiệu công suất, hay còn gọi là tín hiệu công suất trung bình hữu hạn, là những tín hiệu không có năng lượng xác định, với điều kiện 0 < P x < ∞ Chúng bao gồm các tín hiệu có thời gian tồn tại vô hạn, trong đó khi t x → ∞, giá trị tiến tới một hằng số khác không, cùng với các tín hiệu tuần hoàn.
Trong bài viết này, chúng ta sẽ xem xét các ví dụ về tín hiệu liên tục và các thông số liên quan Tín hiệu năng lượng có bốn thông số đặc trưng, trong khi tín hiệu công suất chỉ có hai Tuy nhiên, đối với tín hiệu năng lượng, người ta chủ yếu quan tâm đến hai thông số là tích phân và năng lượng.
Tín hiệu xác định thực và phức
2.2.1 Tín hiệu xác định thực
Hình 2.6 b Tín hiệu năng lượng có thời hạn vô hạn
Hàm mũ suy giảm x (t )={ X x xe −∝t xt x≥ 0 ∝>0
Tín hiệu suy giảm theo hàm mũ x (t )={ X x xe −at x.sin ( ωt 0 t ) t x≥ 0
2.8 c Tín hiệu năng lượng có thời hạn vô hạn
Tín hiệu Sa( ωt 0 t ¿ x (t )=Sa¿ x= π x; xE x = π ωt 0 ωt 0
Tín hiệu công suất
2.3.1 Tín hiệu công suất không tuần hoàn
1 T 1 1 ¿ x≥ log T x→∞ 2T ∫ 0 dt= 2 ; xP x = 2Tín hiệu bước nhảy x ( t ) = X 1 ( t−t 0 ):
Hàm mũ tăng dần: x (t )={ X x ( 1−e −at ) t x≥ 0 ; a > 0
Tín hiệu phân bố
Tín hiệu phân bố δ ( t−t 0 ) : δ ( t−t 0 )={ 0 t x≠ xt
2 phân bố lược ||| (t) bố lược |||(t)
Tín hiệu phân bố lược T 1 ∨¿∨ ( Tt ) :
2 Tính chất lặp tuần hoàn
Tín hiệu xác định phức
Năng lượng của tín hiệu phức:
Phân tích tương quang
2.6.1 Hệ số tương quan giữa hai tín hiệu:
Hệ số tương quan chuẩn hóa: a=a x xa = x x, xy xy x,x xy yx x x,x xy x, xy Điều kiện hệ số tương quan a: 0 ≤ xa≤1 a=1≤¿ x= y a=0≤¿ x xvà y trực giao
2.6.2 Hàm tương quan: a Hàm tương quan của tín hiệu năng lượng
1 φ xy (τ )=φ xy ∗(−τ ) vớitín xhiệuthực xφ xy ( τ )=φ xy
Hàm tự tương quan của tín hiệu thực là hàm chẵn
4 | φ x ( τ ) ∨≤ xφ x ( 0 ) ∀ xτ b Hàm tương quan của tín hiệu công suất không tuần hoàn
Hàm tương quan: ψ xy (τ )lim ¿ T x→ x∞ 21
Phân tích phổ tín hiệu
2.7.1 Phổ tín hiệu năng lượng Định nghĩa : Phổ của tín hiệu năng lượng được xác định bởi biến đổi thuận Fourier Biến đổi Fourier là một công cụ toán được định nghĩa là một cặp biến dổi thuận – ngược như sau:
x(t) & X( ωt¿ :gọi là cặp biến đổi Fourier
1 Nếu x(t) là tín hiệu thực thì P( ωt ¿,∨X ( ωt ) ∨¿ : hàm chẵn theo ωt,Q (ωt) ,φ (ωt ): hàm xlẻtheo xωt x(-t) X(-
5 Tính chất đồng dạng(tỷ lệ): x ( at ) ≤¿ | a | X (aωt)
6 Định lý dịch chuyển trong miền thời gian: x ( t−t 0 )≤¿ X (ωt) e − jωtωtt 0 x ( t+t 0 ) ≤¿ X (ωt)e x jωtωtt 0
7 Định lý dịch chuyển trong miền tần số: x (t ) e x jωt xωt 0 t ≤¿ X ( ωt−ωt 0 ) x (t ) e − jωt xωt 0 t ≤¿ X (ωt +ωt 0 ) x (t ) cos ( ωt 0 t )≤¿ 1 ¿¿ 2 x (t ) sin ωt xt ≤¿ 1 ¿¿
8 Định lý Vi phân trong miền tần số:
9 Định lý Vi phân trong miền thời gian: d n x x ( n t)
10 Định lý tích phân trong miền thời gian
11 Tích chập trong miền thời gian x (t )∗ y (t )≤¿ X (ωt )Y (ωt)
12 Tích chập trong miền thời gian x (t ) y (t )≤¿ 21 π [ X (ωt)∗Y ( ωt)]
13 Định lý về hàm tương quan:
14 Định lý về hàm tự tương quan:
15 Định lý về tích vô hướng;
hiệu ngẫu nhiên
Tín hiệu ngẫu nhiên
Biến ngẫu nhiên là một đại lượng thực có giá trị phụ thuộc vào các biến cố ngẫu nhiên, cho phép chúng ta mô tả các sự kiện này một cách có định hướng.
Sự phụ thuộc này được biểu diễn bởi quy luật xác suất gọi chung là phân bố
Sự phân bố của biến NN được mô tả bởi hàm mật độ xác xuất P X (x)
Hai biến ngẫu nhiên quan trọng và Pdf của chúng
1 Biến ngẫu nhiên đồng nhất
Liên tục : Px (x) = b− 1 a xfor xa≤ xx≤ xb
Rời rạc : P ( X = x I ) = M 1 ,for xX ∈ { x 0 , x…… xx M−1 }
Hàm hai biến A, t là một tín hiệu trong miền thời gian liên quan đến một sự kiện ngẫu nhiên Nó thường được ký hiệu là X(t) và được thể hiện bằng cách nhúng A vào quá trình ngẫu nhiên tĩnh.
- Các tham số trung bình không phụ thuộc vào thời gian
- Đây là quá trình ngẫu nhiên tĩnh (tín hiệu)
Thường có thể mô tả thuận tiện chỉ bằng các tham số trung bình
1 Hàm hai biến m x (t) = E {X (t) } (cố định ) →m x hằng số 2
R x ( τ ¿ = E {X (t) X ( t + τ )} ii Mật độ phổ công suất
Cách duy nhất cho miền tần số mô tả của tín hiệu ngẫu nhiên
3.3 Mật độ phổ công suất
Các thông số và ý nghĩa vật lý của chúng
Trung bình và phương sai của biến ngẫu nhiên
Trung bình, tự tương quan , PSD của quá trình ngẫu nhiên
1 m x Mức DC của tín hiệu
2 E { X 2 (t ), R X ( 0 ) , ∫ G x ( x ) df : Công suất tín hiệu trung bình
3 σ 2 x : Công suất trung bình của thành phần AC
Trong hệ thống thông tin liên lạc, tín hiệu không có thành phần DC có thể được biểu diễn với giá trị trung bình bằng 0, trong khi công suất tín hiệu trung bình được xác định bởi σ²x = E{X²(t)} Bên cạnh đó, tiếng ồn Gaussian trắng (AWGN) là loại tiếng ồn thêm vào tín hiệu, ảnh hưởng đến chất lượng truyền tải thông tin.
Trắng: Có PDS không đổi
Gaussian: trong mọi khoảnh khắc, tiếng ồn là biến ngẫu nhiên Gaussian
Mô hình tín hiệu : y(t) = x(t) +n(t) i) PSD : G n (f) = N 2 0 ii) Tự tương quan : Rn ( τ ¿ = N 2 0 δ (τ )
Tiếng ồn trong hệ thống thông tin liên lạc
Tiếng ồn thường có giá trị bằng 0 nghĩa là AWGN
AWGN là một mô hình nhiễu trừu tượng hữu ích, mặc dù nó không thực tế do sức mạnh vô hạn
Qúa trình rời rạc khi δ ( 0 ) =1 σ 2 =E { X 2 }= N
Công suất và phương sai đều là N 0
3.4 Truyền tín hiệu qua hệ thống tuyến tính
3.4.3 Truyền không biến dạng và bộ lọc ý tưởng
Thời gian : chỉ sự thay đổi cường độ không đổi và độ trễ
Miền tần số : đáp ứng cường độ không đổi và tuyến tính giai đoạn hồi sinh y(t) = K X ( t - t 0 )
Bộ lọc lý tưởng : không biến dạng trong băng thông
Vòng-Cyclic Code
Mô tả
(Cyclic Codes) là một họ mã có ứng dụng đặc biệt rộng rãi trong thông tin.
Mã cyclic, hay mã chu kỳ, là một loại mã tuyến tính đặc biệt có tính chất dịch vòng, nghĩa là một từ mã cũng là một từ mã khác Mã này được công nhận vì những đặc điểm nổi bật của nó.
- Mạch mã hoá và tính syndrome (hội chứng) có thể được thực hiện dễ dàng nhờ bộ ghi dịch có hồi tiếp (feedback connection).
Mã tuyến tính C(n, k) là một loại mã mà khi dịch vòng một từ mã của C, kết quả vẫn là một mã véc tơ thuộc C Nhờ vào cấu trúc của mã, có thể tìm ra nhiều phương pháp khác nhau để giải mã hiệu quả.
Cho véc tơ mã v = (v 0 ,v 1 , v n-1 ), các thành phần của véc tơ mã này có thể xem như là hệ số của đa thức v(x): v(x) = v 0 + v 1 x + + v n-1 x n-1
Mỗi véc tơ mã v có chiều dài n tương ứng với đa thức mã v(x) có bậc tối đa là n-1 Nếu hệ số vn-1 khác 0, bậc của v(x) sẽ là n-1; ngược lại, nếu vn-1 bằng 0, bậc của v(x) sẽ nhỏ hơn n-1.
Sự tương đương 1-1 giữa véc tơ mã v và đa thức mã v(x) cho phép gọi v(x) là đa thức mã (code polynomial) của véc tơ mã v Do đó, véc tơ mã và đa thức mã có thể được sử dụng thay thế cho nhau.
Ví dụ: Mã tuyến tính ở bảng 1 được goi là mã vòng
Khối tin Véc tơ mã: v Đa thức mã v(x)
Bảng 1:Mã vòng với đa thức sinh g(x) = 1 + x + x 3
Một số tính chất đại số quan trọng của đa thức mã bao gồm các định lý sau: Định lý 1 khẳng định rằng đa thức mã khác 0 có bậc nhỏ nhất là duy nhất Theo Định lý 2, nếu g(x) là đa thức mã nhỏ nhất của C(n, k), thì hệ số g 0 phải bằng 1 Định lý 3 chỉ ra rằng một đa thức nhị phân có bậc nhỏ hơn hoặc bằng n-1 là đa thức mã nếu và chỉ nếu nó là bội của g(x) Định lý 4 xác định rằng tồn tại một và chỉ một đa thức mã có bậc n - k Định lý 5 cho biết rằng đa thức sinh g(x) của một C(n,k) là thừa số của x n +1 Cuối cùng, Định lý 6 xác nhận rằng nếu g(x) là đa thức bậc (n-k) và là thừa số của x n +1, thì g(x) sinh ra mã vòng C(n, k).
Ma trận sinh và ma trận kiểm tra của
Gọi g(x) là đa thức sinh bậc n-k của C(n,k) Một khối dữ liệu k phần tử (m0, m1, mk-1) có thể được xem là một đa thức thông tin: m(x) = m 0 + m 1x + + mk-
1xk-1 Việc mã hoá thông qua việc nhân đa thức thông tin với đa thức sinh Kết quả ta có:
Tích đa thức trên được biểu diễn dưới dạng tích ma trận như:
Dạng tổng quát của ma trận sinh G của C(n,k) là: g 0 g 1 g 2 gn−k 0 0 0
( với g0 = gn-k = 1) Trường hợp tổng quát G không có dạng hệ thống Tuy nhiên có thể chuyển G về dạng hệ thống bằng phép biến đổi hàng của ma trận.
Ví dụ: Xét C(7, 4) cho ở bảng 1 với đa thức sinh g(x) = 1 + x + x 3 có ma trận như sau:
G= [ 1 1 0 1 0 0 0 ]Ta thấy G không có dạng hệ thống.
10 Nhưng nếu dùng phép biến đổi hàng: h 3 = h 3 + h 1 và h 4 = h 4 + h 1 + h 2 ta thu được Ma trận G’ có dạng hệ thống như sau:
]Với g(x) là thừa số của xn + 1, có: x n + 1 = g(x).h(x)
10 Với đa thức h(x) có bậc là k được biểu diễn như sau: h(x) = h 0 + h 1 x + + h k x k , (với h 0 = h k = 1) Cho v = (v 0 , v 1 , v n-1 ) là véc tơ mã của C Khi đó v(x) = m(x).g(x) Nhân v(x) với h(x)
Do bậc của v(x) nhỏ hơn hoặc bằng k-1, các giá trị x k, x k+1, , x n-1 không xuất hiện trong biểu thức m(x) + x k.m(x) Khi khai triển v(x).h(x), hệ số của các giá trị x k, x k+1, , x n phải bằng 0, dẫn đến n-k phương trình: h i v n-i-j = 0, với i, j thuộc n-k.
Hàm số ngược của h(x) là: x k.h(x -1 ) = hk + hk-1x + hk-2x 2 + + h0x k
Dễ dàng nhận thấy rằng x k h(x -1 ) cũng là thừa số của (x n + 1) Vậy đa thức sinh xkh(x -1 ) sinh ra (n,n-k) với ma trận H(n-k) x n là ma trận sinh:
Mỗi véc tơ mã của mã C đều trực giao với các hàng của ma trận H, cho thấy H là ma trận kiểm tra chẵn lẻ của C Ma trận H được tạo ra từ đa thức h(x), do đó h(x) được gọi là đa thức kiểm tra của mã C Theo định lý 7, nếu C là mã (n,k) với đa thức sinh g(x), thì mã đối ngẫu của C cũng có thể được sinh ra bởi đa thức x^k.h(x -1), trong đó h(x) được xác định bởi công thức h(x) = (x^n + 1)/g(x).
Mã hoá
Mã hoá (n,k) dạng hệ thống gồm ba bước:
Bước 1: Nhân đa thức thông tin u(x) với x n-k
Bước 2: Chia x n-k u(x) cho g(x) nhận được phần dư b(x).
Bước 3: Hình thành từ mã b(x) + x n-k u(x).
Tất cả ba bước này có thể thực hiện bằng mạch chia với thanh ghi dịch n-k tầng có hàm hồi tiếp tương ứng với đa thức sinh g(x): g(x) = 1 + g 1 x + g 2 x 2 + + g n-k-
Sơ đồ mã hoá được chỉ trong hình 1
Là một khâu của thanh ghi dịch (flip-flop)
Mối liên kết (g = 0:không có sự liên kết, g= 1 có sự liên kết)
Hình 1: Mạch mã hoá vòng (n,k) với đa thức sinh: g(x) = 1 + g 1 x + g 2 x 2 + + g n-k-1 x n-k-1 + x n-k
Các bước tạo mã dùng đa thức sinh như sau:
Bước đầu tiên trong quy trình truyền thông là đóng cổng để tiếp nhận thông tin, với các chữ số thông tin được biểu diễn dưới dạng đa thức u(x) = u0 + u1x + u2x² + + uk-1xk-1 Thông tin này được dịch vào mạng và đồng thời kết nối với kênh truyền Sau khi thông tin u(x) được đưa vào mạch từ thiết bị đầu cuối, nó sẽ được nhân với xn-k Lưu ý rằng ngay khi thông tin được đưa vào, n-k chữ số còn lại trong thanh ghi sẽ đại diện cho các số kiểm tra chẵn lẻ.
Bước 2: Cắt đứt đường hồi tiếp bằng cách điều khiển cho các cổng gi (hở không cho thông tin qua).
Bước 3: Dịch các con số kiểm tra chẵn lẻ để tạo ra đường truyền Những chữ số kiểm tra này kết hợp với k chữ số thông tin, hình thành nên véc tơ mã.
Ví dụ: Xét một mạch mã hoá (7,4) với đa thức sinh g(x) = 1 + x + x 3 như hình dưới
Hình 2: Mạch mã hoá (n = 7, k = 4) với đa thức sinh g(x) = 1 + x + x 3
Việc mã hoá cũng có thể thực hiện bằng cách sử dụng đa thức kiểm tra chẵn lẻ h(x) = h 0 + h 1 x + + h k x k Có thể coi công thức:
Vn-k-j = hivn-i-j = 0, với i j n- k là luật để xác định n-k chữ số kiểm tra chẵn lẻ v 0 ,v 1 , v n-k-1 Hình 3 là mạch mã hoá có hệ số h(x) là các kết nối hồi tiếp.
Nguyên lý hoạt động của mạch và các bước mã hóa dùng đa thức kiểm tra như sau:
Bước 1: Cổng 1 đóng, cổng 2 hở, k chữ số thông tin u(x) = u0 + u1x + +uk-1x k-
1 được dịch vào thanh ghi đồng thời truyền ra kênh thông tin.
Bước 2: Ngay sau khi toàn bộ các chữ số thông tin được dịch vào thanh ghi Cổng
1 hở, cổng 2 đóng, chữ số kiểm tra đầu tiên là:
Vn-k-1 được tạo thành và xuất hiện tại điểm P.
Bước 3: Thanh ghi dịch vòng một bit, trong đó chữ số kiểm tra được chuyển vào kênh thông tin và đồng thời cũng được dịch vào thanh ghi Chữ số kiểm tra thứ hai sẽ được xác định.
Vn-k-2 được tạo thành và xuất hiện tại diểm P.
Bước 4: Lặp lại bước 3 cho đến khi n-k chữ số kiểm tra được tạo ra và dịch vào kênh thông tin.
Hình 3: Mạch mã hoá (n, k) dựa vào đa thức kiểm tra h(x) = 1 + h 1 x + + x k Để minh hoạ, xét ví dụ sau:
Hình 4 là sơ đồ mã hoá cho (7,4) có đa thức sinh g(x) = 1 + x + x3 dựa vào đa thức kiểm tra: h(x) = x 7 /1 + x + x 3 = 1 + x + x 2 + x 4
Mỗi từ mã được biểu diễn dưới dạng v = (v0, v1, v2, v3, v4, v5, v6), trong đó v3, v4, v5, v6 chứa thông tin, còn v0, v1, v2 là các số dùng để kiểm tra tính chẵn lẻ (parity) Phương trình xác định bởi các số kiểm tra này rất quan trọng trong việc đảm bảo tính chính xác của dữ liệu.
Giả sử thông tin cần mã hoá là (1011) thì: v 3 = 1, v 4 = 0, v 5 = 1, v 6 = 1.
Chữ số kiểm tra đầu tiên là: v 2 = v 6 + v 5 + v 4 = 1 + 1 + 0 = 0
Chữ số kiểm tra thứ hai là: v 1 = v 5 + v 4 + v 3 = 1 + 0 + 1
Chữ số kiểm tra thứ ba là: v0 = v4 + v3 + v2 = 0 + 1 + 0 = 1
Vì vậy từ mã tương ứng với thông tin (1011) là (1001011)
Hình 4: Mạch mã hoá vòng (n=7, k=4) dựa vào đa thức kiểm tra h(x) = 1 + x + x 2 + x 4
Giải mã vòng
Việc giải bao gồm ba bước như việc giải mã khối tuyến tính:
Bước 2: Dựa vào syndrome để xác định véctơ lỗi.
Bước 3: Sửa lỗi bằng cách thực hiện phép cộng modul-2 giữa véctơ lỗi và véctơ nhận được, từ đó tạo ra véctơ thông tin thực sự được truyền đi Nếu sửa từng bit một, chỉ cần sử dụng một cổng XOR; trong khi đó, nếu thực hiện sửa lỗi theo cách song song, cần phải sử dụng n cổng XOR.
Cấu trúc cho phép giải mã véctơ nhận r(x) = r 0 + r 1 x + r 2 x 2 + + r n-1 x n-1 một cách tuần tự Những bit nhận được sẽ được giải mã lần lượt bởi cùng một mạch giải mã.
Ngay sau khi tính toán syndrome, mạch giải mã kiểm tra sự tương ứng của syndrome s(x) với véctơ sửa e(x) = e0 + e1x + e2x^2 + + en-1x^(n-1), trong đó có một lỗi ở vị trí cao nhất xn-1 (e n-1 = 1) Nếu s(x) không có sai ở vị trí bậc cao nhất (e n-1 = 0), thì giá trị sẽ được lưu giữ trong thanh ghi đệm và thanh ghi syndrome sẽ dịch chuyển một lần Như vậy, r(1)(x) = r0x + r1x^2 + + rn-2x^(n-1) và đa thức syndrome mới của r(1)(x) là s(1)(x) Lúc này, bit thứ hai rn-2 của r(x) trở thành bit đầu tiên của r(1)(x) Mạch giải mã cũng sẽ kiểm tra s(i)(x) có tương đương với véctơ sai số với lỗi tại vị trí xn-1 hay không.
Nếu syndrome s(x) của r(x) cho thấy một véctơ sai tại vị trí x n-1, thì bit đầu tiên nhận được r n-1 là bit sai và cần được sửa Quá trình sửa lỗi được thực hiện bằng cách tính tổng r n-1 e n-1 Đa thức sửa lỗi được biểu diễn như sau: r1(x) = r 0 + r 1 x + r 2 x^2 + + r n-2 x^(n-1) + (r n-1 e n-1)x^(n-1).
Sau khi lỗi ở bit en-1 được loại bỏ khỏi syndrome s(x), ta thực hiện việc cộng modul syndrome của e’(x) = xn-1 với s(x) Kết quả của phép cộng này là đa thức đã sửa sai r1(x) Tiếp theo, ta tiến hành dịch vòng r1(x) cùng với việc dịch vòng thanh ghi syndrome Kết quả của quá trình dịch vòng sẽ cho ra r1(1)(x) = (rn-1en-1) + r0x + + rn-2xn-1.
Khi thêm 1 vào cuối bên trái của thanh ghi syndrome trong quá trình dịch vòng, ta thu được s 1(1) (x) Mạch giải mã bắt đầu giải mã các bit nhận được r n-2, tương tự như việc giải mã rn-1 Khi phát hiện và sửa lỗi, thanh ghi syndrome sẽ thay đổi, và quá trình giải mã sẽ dừng lại sau n lần dịch vòng Nếu e(x) là véctơ lỗi đã được sửa, thanh ghi syndrome sẽ bằng 0, cho phép nhận được r(x) được giải mã chính xác Ngược lại, nếu quá trình giải mã kết thúc với syndrome khác 0, lỗi sai sẽ được phát hiện nhưng không thể sửa được.
Bộ giải (n,k) có sơ đồ như hình 5 gồm các khối:
- Bộ phát hiện véctơ lỗi.
- Thanh ghi đệm lưu giữ véctơ nhận.
Hình 5: Bộ với đa thức nhận được ở đầu thu r(x) được dịch vào thanh ghi syndrome từ bên trái.
Thủ tục sửa lỗi được mô tả như sau:
Bước 1: Syndrome được tạo ra bằng cách dich toàn bộ véctơ nhận vào thanh ghi syndrome và thanh ghi dệm.
Bộ phát hiện sai là mạch logic có đầu ra là 1 khi syndrome trong thanh ghi syndrome tương ứng với véctơ sai có thể sửa lỗi tại bit bậc cao nhất x n-1 Nếu đầu ra của mạch phát hiện sai là 1, điều đó có nghĩa là bit nhận được là sai và cần phải sửa; ngược lại, nếu đầu ra là 0, bit nhận được là đúng và không cần sửa.
Trong bước 3, bit đầu tiên được dịch ra khỏi thanh ghi đệm, đồng thời thanh ghi syndrome cũng dịch một bit Nếu ký hiệu vừa đọc ra không chính xác, nó sẽ được sửa và đầu ra sẽ nhận được ký hiệu đúng Đầu ra từ mạch phát hiện sai được kết nối hồi tiếp vào thanh ghi syndrome, tạo ra một syndrome tương ứng với véctơ nhận đã dịch sang bên phải.
Bước 4: Syndrome được xác định ở bước 3 sẽ được sử dụng để phát hiện lỗi trong ký hiệu kế tiếp sẽ được đọc từ thanh ghi đệm Mạch giải mã sẽ được lặp lại theo quy trình ở bước 2 và 3.
Trong bước 5, mạch giải mã sẽ tiến hành giải mã từng ký hiệu cho đến khi toàn bộ véctơ nhận r được đọc từ thanh ghi đệm Khi toàn bộ véctơ r đã được đọc ra, nếu thanh ghi syndrome chứa toàn bộ giá trị 0, điều này có nghĩa là véctơ lỗi đã được phát hiện và sửa chữa một cách chính xác.
Ví dụ: Cho (7, 4) với ma trận sinh g(x) = 1 + x + x 3 Mã này có khoảng cách
Hamming nhỏ nhất là 3 và do vậy có khả năng sửa lỗi đơn.
Giả sử chuỗi nhận r(x) = r 0 + r 1 x + r 2 x 2 + r 3 x 3 + r 4 x 4 + r 5 x 5 + r 6 x 6 được dịch vào thanh ghi syndrome từ sang trái Bảng véctơ lỗi và các syndrome tương ứng của chúng được kê ở bảng 2:
Véctơ lỗi Syndrome Véctơ syndrome e(x) s(x) (s0, s1, s2) e 6 (x) = x 6 s(x) = 1 + x 2 101 e 5 (x) = x 5 s(x) = 1 + x + x 2 111 e4(x) = x 4 s(x) = x + x 2 011 e3(x) = x 3 s(x) = 1 + x 110 e 2 (x) = x 2 s(x) = x 2 001 e1(x) = x 1 s(x) = x 010 e0(x) = x 0 s(x) = 1 100
Bảng 2: Véc tơ lỗi và các syndrome tương ứng với đa thức nhận được chuyển vào thanh ghi syndrome từ trái sang phải.
Syndrome s(x) được tính bằng cách lấy phần dư cảu phép chia xi cho g(x) Từ đó suy ra véctơ syndrome tương ứng.
Khi một lỗi đơn xảy ra tại vị trí xi, chuỗi nhập sẽ được chuyển vào thanh ghi syndrome, tạo ra giá trị (101) Tuy nhiên, sau (6 - i) lần dịch, nội dung thanh ghi không còn là (101), do đó cần phải sửa lỗi tương ứng với syndrome (101) Một mạch giải mã hoàn chỉnh đã được thiết kế như hình 6.
Hình 6: Mạch giải mã cho (7,4) với đa thức sinh g(x) = 1 + x + x 2
Miêu tả quá trình giải mã như sau:
Trong ví dụ này, véctơ mã v = (1001011) được truyền thành véctơ nhận r = (1011011), trong đó xuất hiện lỗi đơn tại vị trí x 2 Khi dữ liệu được dịch vào thanh ghi đệm và thanh ghi syndrome, thanh ghi syndrome chứa giá trị (001) Qua quá trình ghi dịch, sau 4 lần dịch, nội dung của thanh ghi syndrome trở thành (101) và mẫu lỗi r 2 sẽ là số tiếp theo xuất khỏi thanh ghi đệm Một nhược điểm của mạch giải mã là thời gian giải mã lâu do phải dịch từng bit một.
Bộ giải mã Meggit là một thiết bị cho phép giải mã dữ liệu từ vị trí bậc cao nhất đến bậc thấp nhất Khi thực hiện quá trình dịch vòng, cả thanh ghi đệm và thanh ghi syndrome sẽ dịch sang phải Đặc biệt, bộ giải mã này cũng có khả năng giải mã ngược, tức là từ vị trí bậc thấp nhất đến bậc cao nhất, trong trường hợp này, thanh ghi đệm và thanh ghi syndrome sẽ dịch sang trái.
Quá trình sửa sai của mạch được mô tả như trên hình vẽ dưới đây:
Phương pháp giải mã Meggit có thể áp dụng cho nhiều loại mã, tuy nhiên, thực tế cho thấy mạch giải mã thường rất phức tạp Do đó, nhiều phương pháp giải mã khác đã được phát triển, bao gồm các biến thể như giải mã bằng phương pháp bẫy lỗi và phương pháp bẫy lỗi cải tiến Tùy thuộc vào từng trường hợp cụ thể, có thể sử dụng một mạch giải mã đơn lẻ hoặc kết hợp nhiều mạch để đáp ứng tốt nhất các yêu cầu của nhiệm vụ.
Phỏng
Ý tưởng
Trong đó: n là độ dài bit (n > k) k là bit thông tin
Với tính linh hoạt và hữu dụng của MATLAB ta có thể áp dụng các giao thức như:
Cyclpoly là một hàm dùng để tìm kiếm một hoặc nhiều đa thức sinh cho các mã tuần hoàn với số bit thông tin n và độ dài k Đối với tất cả các cú pháp, một đa thức được biểu diễn dưới dạng một hàng chứa các hệ số theo thứ tự lũy thừa tăng dần.
Vd : C(n,k) nếu lấy n=7 và k=4 1101 (nếu ở max) và 1011(nếu ở min)
Poly2sym: chuyển đa thức dạng bit sang ký tự
En/Decode: Một trong chức năng có sẵn của MATLAB , hổ trợ người dùng trong việc mã hoá (Linear, Cyclic, Hamming)
Code matlab
clc; clear all; k=input('nhap k'); n=input('nhap n'); m=input('nhap ma');
G=cyclpoly(n,k,'max') gx=poly2sym(G)
Clc: xoá, dọn command window sau mỗi lần chạy lại k: nhập số bit thông tin n: nhập độ dài bit
43 m: nhập mã vào(bit thông tin)
G=cyclpoly là ký tự đa thức vectơ hoặc hàng vectơ cung cấp các hệ số theo thứ tự lũy thừa tăng dần, cho phép điều chỉnh Max, Min và All Hàm gx=poly2sym được sử dụng để chuyển đổi dạng bit của G sang đa thức.
C=encode(m,n,k,'cyclic',G): Mã hoá thông tin vào theo dạng cyclic
Dode(C,n,k,'cyclic',G): Giải mã thông tin của C(encode)