Khóa luận Các phương pháp nén được sử dụng để nén tín hiệu EEG

đi qua cành thấp hơn. Chúng ta xây dựng cây nhị phân bắt đầu tại những nút lá. Như đã biết những từ mã của hai kí tự với xác suất nhỏ nhất là giống nhau ngoại trừ bit cuối cùng. Điều này có nghĩa là việc di chuyển từ gốc tới lá tương ứng với hai kí tự này là như nhau trừ bước cuối cùng. Tức là những lá tương ứng với hai kí tự với xác suất thấp nhất sẽ là con của cùng một gốc. Khi chúng ta kết nối những lá tương ứng với những kí tự có xác suất thấp nhất tới một nút duy nhất, thì chúng ta coi như nút này là một kí tự của bảng chữ đã được giảm bớt. Xác suất của kí tự này sẽ là tổng xác suất của các con của nó. Bây giờ chúng ta sẽ sắp xếp những nút tương ứng bảng kí tự giảm bớt và áp dụng quy tắc như trên để tạo ra một nút bố cho những nút tương ứng với hai kí tự có xác suất thấp nhất trong bảng giảm bớt. Cứ tiếp tục như thế cho đến khi ta thu được một nút duy nhất, đó chính là nút gốc. Để thu được một mã cho mỗi kí tự, chúng ta di chuyển trên cây từ gốc tới mỗi nút lá, bằng cách gán 0 tới cành cao hơn và 1 cho cành thấp hơn Ví dụ : Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29 A B C D E 0.10 0.15 0.30 0.16 0.29 Quá trình xây dựng cây Huffman diễn ra như sau : A B C D E 010 011 11 00 10 èNhư vậy bộ mã tối ưu tương ứng là : 2.3.1.2. Mã số học Một phương pháp khác nhằm tạo ra mã chiều dài biến thiên, phương pháp này ngày càng được sử dụng phổ biến được gọi là phương pháp mã hoá số học (arithmetic coding). Mã số học đặc biệt hữu dụng khi xử lý những nguồn có bảng chữ nhỏ (small alphabets), như là nguồn nhị phân, và bảng chữ có xác suất của các kí tự rất lệch nhau. Nó cũng là một phương pháp rất hữu hiệu khi những vấn đề mô hình (modeling) và mã hoá (coding) của phương pháp nén không mất thông tin (lossless compression) tách rời nhau. Như chúng ta đã nghiên cứu về phương pháp mã hóa Huffman, mà bảo đảm tốc độ mã hóa R trong giới hạn 1 bit của entropy H. Tốc độ mã hóa là số bit trung bình được sử dụng để biểu diễn một kí tự từ nguồn và, đối với một mô hình xác suất đã cho, entropy là tốc độ thấp nhất mà tại đó nguồn có thể được mã hóa. Chúng ta có thể thắt chặt giới hạn này một chút. Nhận thấy rằng thuật toán Huffman sẽ tạo ra một mã mà tốc độ của nó nằm trong giới hạn pmax + 0.086 của entropy, ở đây pmax là xác suất của kí tự xảy ra thường xuyên nhất. Trong nhiều ứng dụng, có khi kích thước bảng chữ là lớn, pmax nhìn chung là khá nhỏ, và độ chênh lệch với entropy, đặc biệt về tỉ lệ tốc độ, là khá nhỏ. Tuy nhiên, có những trường hợp ở đó bảng chữ là nhỏ và xác suất xảy ra của những kí tự khác nhau rất lệch, giá trị của pmax có thể khá lớn và mã Huffman có thể trở nên khá không hiệu quả khi so sánh với entropy. Một cách để tránh vấn đề này là chặn khối nhiều hơn một kí tự với nhau và tạo ra một mã Huffman mở rộng. Tuy nhiên, thực tế không phải phương thức này bao giờ cũng thực hiện được. Tạo ra những từ mã (codewords) cho nhóm hoặc chuỗi kí tự thực sự hiệu quả hơn là tạo ra một từ mã riêng biệt cho mỗi kí tự trong chuỗi. Song phương pháp này trở nên không khả thi khi cố gắng tạo ra mã Huffman cho chuỗi kí tự dài. Để tìm từ mã Huffman cho một chuỗi dài m (sequence of symbols m) riêng biệt chúng ta cần những từ mã cho tất cả những chuỗi chiều dài m có thể. Việc này sẽ làm cho kích thước của sách mã (codebook) tăng theo hàm mũ. Chúng ta cần một phương pháp gán từ mã cho chuỗi riêng biệt này mà không phải tạo những mã cho tất cả các chuỗi có cùng chiều dài. Kĩ thuật mã hoá số học (arithmetic coding technique) sẽ thực hiện được yêu cầu này. Trong mã hoá số học, phải tạo ra một bộ nhận dạng duy nhất hay một nhãn (tag)cho chuỗi được mã hoá. Nhãn này tương ứng với một phân số nhị phân, cái mà sẽ trở thành mã nhị phân của chuỗi. Thực tế việc tạo nhãn và mã nhị phân là hai quá trình giống nhau. Tuy nhiên, chúng ta có thể hiểu dễ dàng hơn phương pháp mã số học nếu về mặt lý thuyết chia phương pháp này thành hai giai đoạn. Trong giai đoạn đầu tạo ra một bộ nhận dạng duy nhất hay nhãn cho chuỗi kí tự đã cho. Sau đó cho nhãn này một mã nhị phân duy nhất . Mã số học duy nhất có thể được tạo ra cho một chuỗi dài m mà không cần phải tạo ra mọi từ mã cho những chuỗi cùng chiều dài. Điều này không giống với mã Huffman. Để phân biệt một chuỗi kí tự này với một chuỗi kí tự khác chúng ta cần phải gán nhãn cho nó bằng một bộ nhận dạng duy nhất. Một tập hợp nhãn có thể dùng biểu diễn những chuỗi kí tự là những số trong khoảng đơn vị [0, 1). Do trong khoảng đơn vị [0, 1) có vô số số, nên có thể gán một nhãn duy nhất cho mỗi kí tự riêng biệt. Để làm điều này chúng ta cần một hàm mà sẽ ánh xạ những chuỗi kí tự vào khoảng đơn vị. Một hàm mà ánh xạ những biến ngẫu nhiên, và chuỗi của biến ngẫu nhiên vào khoảng đơn vị là một hàm phân phối tích luỹ (cdf) của biến ngẫu nhiên của nguồn. Trước khi bắt đầu triển khai mã hóa số học, chúng ta cần phải thiết lập một số kí hiệu. Chúng ta đã biết rằng một biến ngẫu nhiên ánh xạ những kết cục, hay tập hợp những kết cục của một thí nghiệm tới những giá trị trên trục số thực. Sử dụng phương pháp này, chúng ta cần ánh xạ những kí tự nguồn tới những số. Để thuận lợi, chúng ta sử dụng ánh xạ X(ai) = i ai Î A (2.13) Ở đây, A = {a1, a2, …, am} là bảng chữ cho một nguồn rời rạc và X là một biến ngẫu nhiên. Việc ánh xạ này có nghĩa rằng một mô hình xác suất cho trước của nguồn, chúng ta cũng có một hàm mật độ xác suất đối với biến ngẫu nhiên là : P(X = i) = P(ai) Và hàm mật độ tích lũy được xác định như sau : Fx(i) = åik=1 P(X = k) (2.14) Chú ý rằng đối với mỗi kí tự ai với xác suất khác không chúng ta có một giá trị riêng biệt của Fx(i). Chúng ta sẽ sử dụng điều này để sau đó phát triển mã số học. Thủ tục tạo nhãn thực hiện bằng cách giảm kích thước của khoảng mà trong đó nhãn cư trú do càng ngày nhận càng nhiều những phần tử của chuỗi. Hãy bắt đầu bằng việc đầu tiên chia khoảng đơn vị thành những khoảng con có dạng [Fx(i-1), Fx(i)), i = 1, …, m. Vì giá trị cực tiểu của hàm phân phối tích luỹ (cdf) bằng không và giá trị cực đại bằng một, nên việc phân chia phải chính xác khoảng đơn vị. Chúng ta liên kết khoảng con [Fx(i-1), Fx(i)) với kí tự ai. Sự xuất hiện của kí tự đầu tiên trong chuỗi sẽ giới hạn khoảng chứa nhãn từ một trong những khoảng con này. Giả sử rằng kí tự đầu tiên là ak. Sau đó thì khoảng chứa giá trị nhãn sẽ là khoảng [Fx(k-1), Fx(k)). Bây giờ khoảng con này sẽ được phân chia chính xác theo tỉ lệ giống như khoảng nguồn. Có nghĩa là khoảng thứ j tương ứng với kí tự aj được cho bởi [Fx(k-1) + Fx(j-1)/(Fx(k) – Fx(k-1), Fx(k-1) + Fx(j)/(Fx(k) – Fx (k-1)). Vì thế nếu kí tự thứ hai trong chuỗi là aj, thì khoảng chứa giá trị nhãn trở thành [Fx(k-1) + Fx(j-1)/(Fx(k) – Fx(k-1), Fx(k-1) + Fx(j)/(Fx(k) – Fx (k-1)). Mỗi kí tự tiếp theo khiến cho nhãn tương ứng bị giới hạn tới một khoảng mà được phân chia nữa với tỉ lệ giống nhau. Xét Ví dụ: Xét một bảng chữ 3 kí tự A = {a1, a2, a3} với xác suất p(a1) = 0.7, p(a2) = 0.1, và p(a3) = 0.2. Sử dụng phương trình (2.14) ta có Fx(1) = 0.7, Fx(2) = 0.8 và Fx(3) = 1. Sự phân chia này được biểu diễn bằng hình sau: Hình 15: Giới hạn khoảng chứa nhãn cho chuỗi lối vào (a1, a2, a3) Phần con mà nhãn cư trú trong đó phụ thuộc vào kí tự đầu tiên của chuỗi được mã hóa. Ví dụ, nếu kí tự đầu tiên là a1, nhãn sẽ nằm trong khoảng [0.0, 0.7); nếu kí tự đầu tiên là a2, nhãn nằm trong khoảng [0.7, 0.8), nếu là a3, thì nhãn sẽ nằm trong khoảng từ [0.8, 1.0). Khi đã xác định được khoảng chứa nhãn thì những khoảng con còn lại sẽ bị xóa bỏ, và khoảng được giữ lại này lại được phân chia ra thành các khoảng con khác với cùng một tỉ lệ giống như khoảng nguồn. Giả sử kí tự đầu tiên là a1. Nhãn sẽ nằm trong khoảng con [0.0, 0.7). Sau đó khoảng này lại được chia theo tỉ lệ chính xác giống như khoảng nguồn, để tạo ra những khoảng con [0.0, 0.49), [0.49, 0.56), [0.56, 0.7). Khoảng đầu tiên tương ứng với kí tự a1, khoảng thứ hai tương ứng với kí tự a2, và khoảng còn lại [0.56, 0.7) tương ứng với kí tự a3. Giả sử rằng kí tự thứ hai trong chuỗi là a2. Khi đó giá trị nhãn được giới hạn nằm trong khoảng [0.49, 0.56). Bây giờ chúng ta phân chia khoảng này thành các khoảng con theo cùng tỉ lệ như khoảng ban đầu, thu được các khoảng sau : khoảng [0.49, 0.539) tương ứng với kí tự a1, [0.539, 0.546) tương ứng với kí tự a2, và [0.546, 0.56) tương ứng với kí tự a3. Nếu kí tự thứ ba là a3, nhãn sẽ bị giới hạn trong khoảng [0.546, 0.56), sau đó khoảng này có thể sẽ được chia nhỏ hơn nữa. Quá trình này sẽ tiếp tục cho đến khi hoàn thành xong chuỗi nguồn theo cách thức như trên. 2.3.1.3.Kĩ thuật từ điển Kĩ thuật từ điển là một kĩ thuật nén được kết hợp chặt chẽ với cấu trúc trong dữ liệu để tăng lượng nén. Những kĩ thuật này – cả phương pháp tĩnh và thích nghi (adaptive or dynamic) – đều xây dựng một danh sách những mẫu xảy ra phổ biến và mã hóa những mẫu này bằng cách truyền chỉ số của nó trong danh sách. Chúng hữu dụng nhất với những nguồn có một lượng tương đối nhỏ những mẫu được tạo ra khá thường xuyên như là nguồn văn bản và những lệnh máy tính. Trong nhiều ứng dụng, lối ra nguồn bao gồm những mẫu xảy ra liên tiếp. Ví dụ như trong một văn bản có những mẫu hay những từ nào đó tái diễn liên tiếp. Trong khi đó cũng có những mẫu hoàn toàn không xuất hiện, hay nếu có thì xảy ra rất hiếm khi. Cho nên đối với những loại nguồn này một phương pháp rất hợp lý để mã hóa nó là giữ một danh sách hay từ điển những mẫu xảy ra thường xuyên. Khi những mẫu này xuất hiện trong lối ra nguồn, chúng sẽ được mã hóa bằng việc tham chiếu đến bảng từ điển. Nếu mẫu này không xuất hiện trong từ điển, thì nó có thể được mã hóa bằng cách sử dụng một phương pháp khác kém hiệu quả hơn. Trong thực tế chúng ta tách nguồn vào thành hai loại, những mẫu xảy ra thường xuyên và những mẫu xảy ra không thường xuyên. Để phương pháp này có hiệu quả, loại mẫu xảy ra thường xuyên, và do đó kích thước của từ điển, phải nhỏ hơn nhiều so với toàn bộ số mẫu có thể. Giả sử có một nguồn văn bản cụ thể bao gồm những từ có 4 kí tự, 3 kí tự từ 26 chữ cái thường của bảng chữ cái Tiếng Anh theo sau là những dấu phân cách như là dấu chấm (.), dấu phẩy (,), dấu hỏi (?), dấu chấm phẩy (;), dấu hai chấm (:), dấu chấm cảm (!). Hay nói cách khác kích thước bảng chữ nguồn là 32. Nếu chúng ta mã hóa nguồn văn bản mỗi lần một kí tự, coi mỗi kí tự là một sự kiện đồng khả năng, thì chúng ta sẽ cần 5 bit trên một kí tự. Coi tất cả 324 (=220 = 1,048,576) mẫu 4 kí tự (four-character pattern) là đồng khả năng, thì chúng ta sẽ có một mã mà gán 20 bít cho mỗi mẫu 4 kí tự này. Giả sử đặt 256 mẫu 4 kí tự mà có khả năng nhất vào trong từ điển. Lưu đồ truyền thực hiện như sau : bất cứ khi nào muốn gửi một mẫu mà có tồn tại trong từ điển, chúng ta sẽ gửi một bit cờ (flag), giả sử bit 0, theo sau bởi một chỉ số 8 bit tương ứng với mục từ trong từ điển. Nếu mẫu đó không có trong từ điển, chúng ta sẽ gửi bit 1 theo sau bởi 20 bit mã hóa mẫu. Tính hữu dụng của lưu đồ này phụ thuộc vào phần trăm những từ mà chúng ta bắt gặp có trong từ điển. Có thể đánh giá tính hữu dụng này bằng cách tính số bit trung bình trên mỗi mẫu. Nếu xác suất bắt gặp một mẫu trong từ điển là p, thì số bit trung bình trên mỗi mẫu R là : R=9p + 21(1-p) = 21- 12p (2.15) Để sơ đồ này hiệu quả, R phải có giá trị nhỏ hơn 20, khi đó p ≥ 0.084. Giá trị này dường như không lớn. Tuy nhiên, nếu các mẫu xảy ra là đồng khả năng, thì xác suất bắt gặp một mẫu trong từ điển thấp hơn 0.00025. Chúng ta hoàn toàn không muốn một lưu đồ mã hóa mà chỉ thực hiện tốt hơn một chút phương pháp mã hóa thông thường cho những mẫu đồng khả năng; mà chúng ta muốn cải thiện hiệu suất nhiều nhất có thể. Để đạt được điều này, p phải lớn nhất có thể. Có nghĩa là chúng ta phải lựa chon cẩn thận những mẫu có khả năng xảy ra nhất để đưa vào trong từ điển. Do đó chúng ta phải có những hiểu biết khá tốt về cấu trúc lối ra nguồn. Nếu không có thông tin giá trị kiểu này trước khi mã hóa một lối ra nguồn cụ thể, bằng cách này hay cách khác chúng ta cần phải có được thông tin trong khi đang thực hiện mã hóa. Nếu cảm thấy đã có đầy đủ hiểu biết trước, chúng ta có thể sử dụng phương pháp tĩnh (static approach); nếu không, nên sử dụng phương pháp thích nghi (adaptive approach). 2.3.1.4. Phương pháp nén dựa vào ngữ cảnh (context-based compression) Phần này chúng ta sẽ trình bày một phương pháp nén sử dụng tối thiểu những giả thuyết từ trước về thống kê của dữ liệu. Thay vào đó chúng sử dụng ngữ cảnh của dữ liệu đang được mã hoá và lịch sử quá khứ của dữ liệu để cung cấp kĩ thuật nén hiệu quả hơn. Như chúng ta học, chúng ta sẽ nhận được hiệu suất nén càng cao khi bản tin mã hoá có tập hợp xác suất càng “lệch” (“skewed). “Skewed” có nghĩa rằng những kĩ tự có xác suất xảy ra cao hơn so với các kí tự khác trong chuỗi sẽ được nén. Vì thế nó luôn mong đợi những cách biểu diễn bản tin mà sẽ cho kết quả lệch lớn hơn. Một cách rất hiệu quả có thể thực hiện được điều này là xem xét xác suất xảy ra của mỗi một kí tự theo ngữ cảnh mà nó xuất hiện. Có nghĩa là, chúng ta không xem xét mỗi kí tự trong một chuỗi nếu như nó chỉ xảy ra hoàn toàn bất ngờ. Thay vì như thế, chúng ta kiểm tra lịch sử của chuỗi trước khi xác định xác suất có thể của những giá trị khác nhau mà kí tự đó đảm nhận. Trong trường hợp văn bản tiếng Anh, Shannon đã chỉ ra vai trò của ngữ cảnh bằng hai thí nghiệm rất thú vị. Cách đầu tiên, lựa chọn một phần văn bản và yêu cầu một đối tượng nào đó đoán mỗi chữ cái. Nếu người đó đoán đúng, nói cô ấy đúng và chuyển sang chữ cái tiếp theo. Nếu cô ấy đoán sai, nói cho cô ấy biết câu trả lời đúng và lại chuyển sang chữ cái tiếp theo. Đây là kết quả của một trong những thí nghiệm này. Trong đó dấu gạch ngang (dash) biểu diễn những chữ cái đã được đoán đúng Actual text THE ROOM WAS NOT VERY LIGHT A SMALL OBLONG Subject Performance - - - - ROO- - - - - - NOT-V - - - - I - - - - - -SM - - - OBI - - - Lưu ý rằng có một dịp tốt để cho cô ấy đoán đúng chữ cái, đặc biệt nếu chữ cái nằm ở cuối một từ hay nếu theo ngữ cảnh từ đó rất rõ ràng. Bây giờ nếu chúng ta biểu diến chuỗi nguồn bằng hiệu suất đoán, chúng ta sẽ nhận được một tập hợp xác suất khác nhau đối với những giá trị mà mỗi thành phần của chuỗi đảm nhận. Xác suất dứt khoát sẽ lệch hơn nhiều trong hàng thứ hai: “chữ cái” - xảy ra với xác suất cao. Nếu cặp đôi toán học của đối tượng có sẵn ở một điểm cuối khác, chúng ta có thể gửi câu “ lược bỏ” ở dòng thứ hai và có cặp đôi được thông qua quá trình đoán như nhau để tiến đến chuỗi kí tự nguồn. Trong thí nghiệm thứ hai, cho phép đối tượng tiếp tục đoán cho đến khi cô ấy đoán được chữ cái đúng và số lượng đoán cần đến để đoán đúng chữ cái sẽ được ghi nhớ. Hơn nữa, hầu hết những lần đoán đúng, thì kết quả là 1 là số có thể nhất. Sự tồn tại của cặp đôi toán học tại điểm kết thúc nhận sẽ cho phép chuỗi lệch này biểu diễn chuỗi nguồn tại bộ nhận. Shannon đã sử dụng thí nghiệm của mình để tiến đến giới hạn trên và dưới cho bảng chữ cái tiếng Anh (lần lượt là 1.3 bit /chữ cái và 0.6 bit / chữ cái) Cái khó trong việc sử dụng những thí nghiệm này là đối tượng đoán là người dự đoán kí tự tiếp theo trong chuỗi tốt hơn nhiều bất kí một bộ dự đoán toán học nào mà chúng ta có thể triển khai. Giả sử rằng ngữ văn là bẩm sinh đối với mỗi người, ở đó trường hợp phát triển một bộ dự đoán hiệu quả như con người đối với ngôn ngữ là không thể trong tương lai gần. Tuy nhiên thí nghiệm thực hiện cung cấp một phương pháp nén hữu dụng cho nén tất cả mọi loại chuỗi , chứ không chỉ đơn giản cho những biểu diễn ngôn ngữ. Nếu chuỗi kí tự được mã hoá không bao gồm sự xảy ra độc lập của các kí tự, thì những kiến thức về những kí tự đã xảy ra ở lân cận của kí tự đang mã hoá sẽ cung cấp cho chúng ta một hiểu biết tốt hơn nhiều về giá trị của kí tự đang mã hoá. Nếu chúng ta biết được ngữ cảnh trong đó một kí tự xảy ra chúng ta có thể đoán với khả năng thành công lớn hơn nhiều so với giá trị của kí tự. Nói cách khác, trong ngữ cảnh cho trước, một số kí tự xảy ra với xác suất lớn hơn nhiều những chữ khác. Có nghĩa là, sự phân bố xác suất trong ngữ cảnh cụ thể sẽ lệch hơn. Nếu ngữ cảnh được biết ở cả hai bộ mã hoá và giải mã, thì chúng ta có thể sử dụng sự phân bố lệch này để thực hiện mã hoá, vì vậy sẽ tăng mức nén. Bộ giải mã có thể sử dụng những hiểu biết về ngữ cảnh của nó để xác định sự phân bố được sử dụng để giải mã. Nếu chúng ta có thể bằng cách nào đó nhóm những ngữ cảnh giống nhau với nhau, thì rất có thể là những kí tự theo sau những ngữ cảnh này sẽ giống nhau, cho phép sử dụng chiến lược nén đơn giản và hiệu quả. Chúng ta có thể nhận thấy ngữ cảnh đóng vai trò quan trọng trong việc nâng cao hiệu quả nén. Xem xét việc mã hoá từ “probability”. Giả sử chúng ta đã mã hoá bốn chữ cái đầu tiên và muốn mã hoá chữ cái thứ năm , “ a”. Nếu chúng ta bỏ qua bốn chữ cái đầu tiên, xác suất của “a” là 0.06. Nếu chúng ta sử dụng thông tin về chữ cái trước nó là “b”, thì sẽ làm giảm xác suất của vài kí tự giống như là q và z và tăng xác suất xảy ra của “a”. Trong ví dụ này, “ b” sẽ là ngữ cảnh bậc nhất đối với “a”, “ob” là ngữ cảnh bậc hai đối vói “a”, vân vân….Sử dụng nhiều chữ cái hơn để xác định ngữ cảnh mà “a” xảy ra, hay những ngữ cảnh bậc cao, nhìn chung sẽ làm tăng xác suất xảy ra của a trong ví dụ này, và vì vậy làm giảm số bit yêu cầu để mã hoá sự xảy ra đó. Vì vậy chúng ta muốn làm những gì để mã hoá mỗi kí tự sử dụng xác suất xảy ra của nó đối với ngữ cảnh bậc cao. 1.4. Đo chất lượng nén Do yêu cầu cần phải khôi phục lại tín hiệu EEG sau khi nén là chính xác, không đánh mất bất kì một thông tin nào. Nên các phương pháp được nghiên cứu là những phương pháp nén không mất thông tin (lossless compression). Vì vậy trong giới hạn khoá luận này, chúng ta sẽ chỉ trình bày những đại lượng được đưa ra để đo hiệu quả của mỗi kĩ thuật nén lossless. Đối với những thuật toán nén không mất thông tin, chúng ta đo hiệu quả nén bằng số lượng co lại của file nguồn so với kích thước file nén. Một số phương pháp sau : Tỉ lệ nén. Compression ratio = (2.18) Hệ số nén Compression factor = (2.19) Phần trăm tiết kiệm %tiết kiệm = (2.20) CHƯƠNG 3: NÉN TÍN HIỆU EEG 3.1. Các phương pháp đã được sử dụng để nén EEG 3.1.1. Các phương pháp nén không mất thông tin (lossless compression) 3.1.1.1. Giới thiệu phương pháp nén Như chúng ta đã biết tín hiệu EEG ghi lại các hoạt động điện của não nhằm phục vụ các nghiên cứu về não, hay chẩn đoán và điều trị bệnh nhân có rối lọan não. Ví dụ như, chuẩn đoán động kinh và vị trí não bị tổn thương liên quan đến rối loạn này. Một đặc điểm của tín hiệu EEG đo được trên người bị động kinh là có sự xuất hiện đột ngột, bất thường, quá mức của các xung động kinh như gai (Spike) hay phức hợp gai-sóng đứng (Spike and sharp wave complex). Vì thế, khi nén tín hiệu EEG phục vụ cho động kinh, các thông tin về các xung liên quan đến bệnh động kinh cần được bảo toàn đọ chính xác. Hay nói cách khác, kĩ thuật nén EEG yêu cầu khôi phục lại hoàn toàn dạng sóng từ dữ liệu được nén. Trong bài báo cáo này, những kĩ thuật nén dữ liệu EEG mà cho phép khôi phục lại hoàn toàn dạng sóng ghi được từ dữ liệu được nén sẽ được trình bày và thảo luận. Nén dữ liệu cho phép chúng ta có thể đạt được việc giảm đáng kể không gian được yêu cầu để lưu trữ tín hiệu và giảm thời gian truyền. Kĩ thuật mã Huffman kết hợp với việc tính toán ban đầu đã đạt đựơc tỉ lệ nén cao (trung bình khoảng 58% đối với tín hiệu EEG) với mức độ phức tạp tính toán thấp. Bằng cách khai thác kết quả này một sơ đồ mã hoá / giải mã (coder/decoder) nhanh, đơn giản có khả năng thực hiện thời gian thực trên PC được thực thi: Dữ liệu nguồn (EEG signal) Source binary file Compressed binary file Compression (coding) Hình 16 : data EEG in compression Compressed binary file Reconstructed binary file Decoded data in file (EEG signal) Decompression (decoding) Hình 17 : data EEG in decompression Kĩ thuật đơn giản này được so sánh với những phương pháp nén khác như những phép biến đổi dự đoán (predictive transformations), lượng tử hóa véc-tơ (vector quantization), biến đổi cosin rời rạc (discrete consine transform) và những phương pháp nén đếm lặp (repetition count compression methods). Từ đó, người ta chỉ ra rằng cây Huffman “collapsed” cho phép thuật toán nén có thể lựa chọn chiều dài từ mã dài nhất mà không ảnh hưởng nhiều đến tỉ lệ nén. Vì vậy những bộ vi xử lý rẻ tiền và những thiết bị lưu trữ có thể sử dụng hiệu quả để lưu trữ những tín hiệu EEG dài trong dạng nén. Khi nén tín hiệu EEG, một yêu cầu cần được đảm bảo là không được cản trở việc khôi phục hoàn toàn thông tin gốc từ dữ liệu đã nén. Những kĩ thuật nén này được gọi là nén không mất thông tin (lossless compression). Bình thường ta có thể sử dụng đo 32 kênh (là số lượng điện cực chuẩn đo), với độ chính xác là 8-b, tại tốc độ lấy mẫu là 1kHz. Tuy nhiên trong thực tế, ta có thể sử dụng số lượng kênh ít hơn và tốc độ bit thấp hơn cũng đủ. Trong bài báo cáo này chúng ta sẽ đề cập đến tốc độ lấy mẫu là 128 Hz/kênh, độ chính xác 8-b, 20 kênh (luồng dữ liệu 20 480 bps), mà được xem như là đủ để đạt được chất lượng tín hiệu EEG tốt. Bên cạnh nén không mất thông tin, những kĩ thuật nén mất thông tin (lossy compression) có thể bảo quản được những thông tin quan trọng để đảm bảo rằng tránh được lỗi chẩn đoán. Tuy nhiên, do hiện tại thiếu một luật lệ và chấp nhận một tiêu chuẩn nào, nên trong tiến hành chữa bệnh các bác sĩ cân nhắc việc khôi phục EEG chính xác là một yêu cầu cần thiết trước tiên để thực hiện nén tốt hơn. Nén dữ liệu lossless EEG đã được nghiên cứu sâu. Vì vậy, những thuật toán nén (đếm lặp, mã Huffman), lượng tử hóa vectơ và những kĩ thuật được sử dụng rộng rãi đã dựa trên những bộ mã dự đoán tín hiệu (những bộ dự đoán tuyến tính, khả năng cực đại, mạng nơron) đã được thực hiện và đánh giá. Những bộ nén dữ liệu được so sánh với 2 chương trình nén được sử dụng rộng rãi là gzip và Iharc. Đầu tiên là dựa vào mã Lempel-Ziv và đã được phát triển dưới dự án GNU, bởi FSF (Free softwave Foundation), sau đó dựa vào mã Huffman và được phát triển bởi Tagawa. Sau đây, Một tiêu chuẩn được sử dụng để đo mức độ nén dữ liệu được xác định là: (3.1) Ở đây Lorig và Lcomp là chiều dài của file nguồn và file đã nén Thực hiện nén tín hiệu bằng việc loại bỏ những dư thừa được bộc lộ ở chính bản thân dữ liệu về sự phụ thuộc thống kê giữa các mẫu. Những phương pháp dự đoán khai thác sự phụ thuộc về mặt thời gian và ước lượng mẫu kế tiếp từ những mẫu trước đó. Sự phụ thuộc về không gian giữa những kênh lối vào sẽ được khai thác bằng những phương pháp không mất thông tin dựa vào phương pháp lượng tử hoá vectơ, phương pháp này thực hiện tốt hơn mọi chiến lược nén dữ liệu khác (khoảng 62%). Tuy nhiên, bằng một sơ đồ dự đoán đơn giản, chúng ta có thể đạt được tỉ lệ nén khoảng 58%, cho phép thực hiện một bộ nén thời gian thực Để giải quyết khó khăn về sự hạn chế chặt chẽ thời gian, một mã chiều dài từ cực đại đã được thiết kế. Kết quả là 16 b đủ để nén hiệu quả tín hiệu EEG với sự mất mát hạn chế về hiệu suất thực hiện. Hơn nữa, bằng chứng thực hiện đã chứng minh rằng những hiểu biết về những tín hiệu sinh học EEG quan trọng có thể chỉ cải thiện một chút tỉ lệ nén. Nén dữ liệu không mất thông tin (lossless compression) có thể đạt được bằng cách gán những mô tả ngắn cho những kí tự thường xuyên xuất hiện nhất của dữ liệu nguồn và những miêu tả dài hơn cần thiết cho những kí tự xuất hiện ít hơn. Đối với mục đích của chúng ta, những sự mô tả này là những xâu nhị phân được biểu diễn bởi mã nhị phân chiều dài thay đổi. Sẽ không mất tính tổng quát nếu chỉ xét đến mã prefix. Những mã này được quan tâm đặc biệt vì chúng đơn giản hóa rất nhiều phép tính mã hóa và giải mã. Thực tế, chúng cho phép nhận ra một từ mã mà không cần biết trước độ dài, khi quét từ trái sang phải những bit của nó không bao giờ thỏa mãn đồng thời vừa là từ mã vừa là tiền tố của từ mã khác. Ví dụ Phép toán cơ bản của một thuật toán cùng cấu trúc dữ liệu được biểu diễn như sau: ENCODER DECODER Input output 00000000 00000001 00000010 00000011 00000100 ………… 1 00 011 1001 110 ……. 00000001 00000010 00000000 0 1 0 1 1 Hình 18: Encoding/decoding scheme Thực hiện mã hóa bằng cách móc nối những từ mã tương ứng với mỗi kí tự của nó trong file và tìm lại được bằng việc truy nhập bảng tra cứu. Việc giải mã với từ mã prefix cũng đơn giản: một cây nhị phân, lá của nó là những kí tự đã cho, là sự biểu diễn mã prefix thích hợp cho thuật toán giải mã. Những bước giải mã là một chuỗi những bước dịch trái hay phải, tùy theo lối vào là 0 hay 1, cho đến khi tới lá. Định lý Shannon biểu diễn giới hạn trên của việc nén dữ liệu được biểu diễn bởi đại lượng entropy, một đại lượng dựa trên sự phân phối xác suất nguồn thông tin, được xác định bằng : H = - (3.2) Ở đây pi là xác suất của kí tự thứ i của bảng kí tự nguồn A= {a1 , a2 , a3 ,…., aM }. Nén đạt mức cực đại bằng : Clim = 1 - (3.3) với b là số bit nguồn cố định trên mỗi kí tự . 3.1.1.2. Phương pháp mã Huffman Sơ đồ mã hóa Huffman tạo ra những mã prefix tối ưu thông qua thuật toán tham lam nhằm khai thác cây