Đề tài Trình bày các phương pháp nén được sử dụng để nén tín hiệu EEG

Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 1 - LỜI MỞ ĐẦU Trong thập kỉ trước nén dữ liệu đã được sử dụng ở khắp mọi nơi. Cĩ thể nĩi rằng nén dữ liệu đã trở thành yêu cầu chung cho các hầu hết các phần mềm ứng dụng, và cũng là một lĩnh vực nghiên cứu quan trọng và hấp dẫn trong khoa học máy tính. Nếu khơng cĩ các kĩ thuật nén dữ liệu thì sẽ khơng bao giờ cĩ sự phát triển của Internet, TV số, truyền thơng di động hay sự phát triển của các kĩ thuật truyền thơng video. Ưu điểm nổi bật và hiệu quả của nén đã được áp dụng và phát triển nhiều lĩnh vực khác như truyền thơng đa phương tiện hay các lĩnh vực nghiên cứu khác. Thời gian gần đây, một lĩnh vực đang phát triển rất nhanh và ngày càng thu hút sự quan tâm của nhiều người đĩ là y tế từ xa (Telemedicine), mà nén đĩng vai trị rất quan trọng. Từ đĩ con người sẽ được chăm sĩc sức khoẻ tốt hơn bằng cách cĩ thể khám, chữa bệnh từ bất kì một bệnh viện nào trên thế giới mà khơng cần phải đến tận nơi đĩ. Chỉ cần giao tiếp với bác sĩ qua thiết bị thu ghi và phương tiện truyền thơng thì sau đĩ sẽ nhận được kết quả chẩn đốn và phương thức chữa bệnh của bác sĩ gửi về. Một trong những tín hiệu EEG quan trọng nhất đĩ là tín hiệu EEG. Và trong bài báo cáo này sẽ trình bày các phương pháp nén được sử dụng để nén tín hiệu EEG. Sự cần thiết của việc này như thế nào sẽ được trình bày sau đây. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 2 - CHƯƠNG 1: GIỚI THIỆU CHUNG 1.1. Nén dữ liệu Nén dữ liệu hay cịn gọi là mã hĩa nguồn (source coding), là sự biểu diễn thơng tin của dữ liệu nguồn dưới dạng nén. Nĩ đã là một cơng nghệ then chốt trong cuộc cách mạng truyền thơng đa phương tiện số trong nhiều thập kỉ. Mục tiêu của nén dữ liệu bao gồm việc tìm ra một thuật tốn hiệu quả để loại bỏ dư thừa tồn tại trong dữ liệu đĩ. Ví dụ cho một xâu kí tự S, thì cái gì là chuỗi kí tự cĩ thể thay thế được để cho ta một khơng gian tích trữ nhỏ hơn? Những giải pháp cho vấn đề này là những thuật tốn nén mà sẽ xuất phát từ chuỗi kí tự cĩ thể thay thế được để thu được số bit ít hơn trong tồn bộ số bit cần biểu diễn, cùng với những thuật tốn giải nén để khơi phục lại dữ liệu ban đầu. Tuy nhiên, ít hơn bao nhiêu bit? Điều đĩ phụ thuộc vào việc lựa chọn thuật tốn mà được sử dụng và lượng dư thừa thơng tin tồn tại trong dữ liệu nguồn. Dữ liệu khác nhau cĩ thể yêu cầu những thuật tốn khác nhau để nhận ra dư thừa và loại bỏ nĩ. Rõ ràng, điều này khiến cho những bài tốn nén trở nên khĩ giải quyết vì yêu cầu chung khĩ được trả lời một cách dễ dàng khi nĩ gồm quá nhiều trường hợp. May mắn thay, chúng ta cĩ thể đưa ra một số ràng buộc nhất định và kết hợp với kinh nghiệm về dữ liệu cũng như mục đích sử dụng dữ liệu để đưa ra những thuật tốn phù hợp. Khi nén dữ liệu, chúng ta cần thiết phải phân tích những đặc tính của dữ liệu được nén và hy vọng suy ra một vài mơ hình để biểu diễn nén. Điều này làm tăng mức độ đa dạng về mơ hình dữ liệu. Do vậy, kĩ thuật biểu diễn là một khâu trọng tâm của kĩ thuật nén. Một cách cụ thể, nén dữ liệu cĩ thể được xem như là một phương pháp biểu diễn hiệu quả một nguồn dữ liệu số như văn bản, hình ảnh, âm thanh hay bất kì một dạng kết hợp nào của tất cả các loại này ví dụ như video. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 3 - Hình 1: data in compression Hình 2: figure of data compression Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 4 - Mục đích của nén dữ liệu là biểu diễn nguồn số này bằng số lượng bit ít nhất cĩ thể khi gặp những yêu cầu tối thiểu để khơi phục lại dữ liệu ban đầu. Lý thuyết thơng tin (information theory) được sử dụng nhiều trong nén dữ liệu. 1.2. Tín hiệu EEG (Electroencephalograph) và Sự cần thiết nén dữ liệu y sinh (Biomedical data compression) Hình 3: system 10/20 Một ứng dụng quan trọng về nén dữ liệu là trong lĩnh vực y học. Yêu cầu nén tín hiệu y-sinh ngày càng cao do sự phát triển ngày càng đa dạng của các dịch vụ y tế từ xa. Những ứng dụng y tế từ xa càng ngày càng dành được nhiều sự quan tâm, nghiên cứu bởi nĩ cung cấp sự truy nhập dễ dàng tới những thủ tục chuẩn đốn bệnh và đánh giá bệnh. Cần phải truyền một lượng lớn dữ liệu y sinh đã thúc đẩy sự cần thiết của việc nén dữ liệu y sinh mà khơng mất thơng tin quan trọng mang trên những tín hiệu ghi đựơc mà cĩ thể dẫn tới hành động chuẩn đốn hay đánh giá bệnh sai. Do đĩ, nghiên cứu về nén tín hiệu y-sinh là rất cần thiết. Một trong những tín hiệu y-sinh phổ biến hiện nay là tín hiệu điện não (EEG- Electroencephalogram). 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 đốn và điều trị bệnh nhân cĩ rối lọan não. Ví dụ như, chuẩn đố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 chứng bệnh rất phổ biến trên thế giới cũng như ở Việt Nam. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 5 - 1.2.1. Tín hiệu EEG Những hoạt động điện của vỏ não thường là những tín hiệu nhịp (rhythms) vì chúng thường dao động lặp đi lặp lại. Sự đa dạng của tín hiệu nhịp EEG vơ cùng lớn và phụ thuộc vào nhiều yếu tố trong trạng thái tinh thần của đối tượng, như là mức độ kích động, trạng thái đi bộ hay trạng thái ngủ. Thơng thường, những tín hiệu được ghi trên da đầu cĩ biên độ nằm trong khoảng từ vài microvolts tới xấp xỉ 100 µV, và tần số trong khoảng từ 0.5 đến 30-40 Hz. Hình 4 : các tín hiệu nhịp EEG Tín hiệu EEG cơ bản được chia thành 5 dải tần sau :  Nhịp Alpha : là nhịp cơ sở của não người lớn. Là dạng sĩng dễ nhận biết nhất, đi thành chuỗi sĩng 8-13 Hz với biên độ 30-50 mV Hình 5: tín hiệu alpha  Nhịp Beta : là sĩng cĩ tần số 4-35 Hz, điện thế khoảng 5-30 mV Hình 6: tín hiệu Beta Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 6 -  Nhịp Delta : là một sĩng chậm dưới 4 Hz và cĩ biên độ thay đổi Hình 7: tín hiệu Delta  Nhịp Theta : bao gồm các sĩng 4-8 Hz , thường cĩ biên độ lớn hơn 20 mV Hình 8: tín hiệu Theta  Nhịp Gamma : cĩ tần số > 30 Hz. Đối với người lớn bình thường thì dải tần của tín hiệu EEG nằm giữa khoảng 0.1-100 Hz. Hầu hết những tín hiệu ở trên duy trì trong vài phút , trong khi cĩ những tín hiệu khác chỉ xảy ra trong vài giây, như nhịp gamma. Ngồi ra cịn cĩ những tín hiệu mà nĩ khơng xuất hiện vào mọi lúc. Nĩ là những tín hiệu nhất thời, đột ngột, biểu thị hoạt động quá mức, khơng bình thường của hoạt động điện của não  Các gai (Spikes) là những biến đổi điện thế thống qua, nhanh, cĩ biên độ thực sự cao hơn hoạt động điện cơ bản. Cĩ khoảng thời gian từ 20 – 70 ms Hình 9: Spike đơn  Sĩng nhọn (Sharp waves) : là những sĩng đơn độc, cĩ khoảng thời gian từ 70 – 200 ms . Cĩ biên độ xấp xỉ bằng với Spikes  Phức hợp sĩng gai (Spike-wave complexes) : là một sĩng phức hợp của một gai (spikes) và theo sau là một sĩng chậm. Cĩ tần số vào khoảng 3- 6 Hz Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 7 - Hình 10: Spike and Sharp wave Sự xuất hiện của các dạng sĩng này chỉ ra những hành động thần kinh sai lệch thường được tìm thấy ở những người phải trải qua những cơn động kinh. Đĩ là những tín hiệu biểu hiện bệnh lý. 1.2.2. Sự cần thiết nghiên cứu nén tín hiệu y sinh Mong muốn nén dữ liệu EEG vì nhiều lý do.Như chúng ta đã biết, EEG là một trong những phương pháp phổ biến giúp bác sĩ cĩ thể xác định vị trí ổ bệnh (khu vực phĩng điện) và chức phận não bệnh nhân bị tổn thương. Là một phương pháp hữu hiệu để phát hiện và chẩn đốn bệnh động kinh - một căn bệnh phổ biến và nguy hiểm. Theo thống kê của Tổ Chức Y tế Thế giới (WHO), tỉ lệ người mắc bệnh động kinh trên thế giới khoảng 0,5% dân số, thay đổi tuỳ theo từng quốc gia, từng vùng, từng dân tộc, như ở Pháp và ở Mỹ là khoảng 0,85%; Canada là 0,6%. Tại Việt Nam khoảng 2% dân số trong đĩ cĩ đến 60% số bệnh nhân là trẻ em. Theo BS Lê Văn Tuấn, chuyên khoa nội thần kinh BV Chợ Rẫy, TP.HCM: Động kinh đơi khi biến chứng và tai nạn cĩ thể gặp khi bệnh nhân lên cơn động kinh: cắn phải lưỡi, viêm phổi do hít phải dãi hay chất nơn ĩi; gãy xương do chấn thương; tổn thương não do cưoin kéo dài làm não thiếu oxy; ngừng thở do tắc nghẽn đường thở… Tuy nhiên, bệnh hồn tồn cĩ thể điều trị nếu được phát hiện sớm và điều trị đúng cách thì khả năng hồn tồn khỏi bệnh là rất cao. Đối với trẻ em, nếu khơng được điều trị kịp thời, hoặc điều trị khơng đúng cách dẫn tới tình trạng khơng khống chế được cơn co giật. Lâu dần, trẻ sẽ bị thiểu năng trí tuệ, rối loạn hành vi. Những cơn co giật sẽ làm cho hệ miễn dịch của trẻ yếu đi, dễ nhiễm các bệnh khác và dễ tử vong hơn trẻ bình thường. Tre bị động kinh khơng được điều trị đúng thuốc, đúng phác đồ nên sinh ra kháng thuốc. Khi đĩ, khả năng hồi phục sẽ khĩ khăn hơn rất nhiều. Do đĩ việc phát hiện kịp thời động kinh, chẩn đốn chính xác bệnh và điều trị hợp lý là vơ cùng quan trọng, cấp bách và cần thiết. Song khơng phải bất kì bệnh viện nào cũng làm được điều đĩ vì nĩ hồn tồn phụ thuộc vào trình độ và khả năng của bác sĩ đọc điện đồ não. Tín hiệu EEG ghi được rất phức tạp bởi bản ghi khơng chỉ cĩ tín hiệu nền cơ bản (alpha, gamma,…), các xung bất thường (spike, sharp…) mà nĩ cịn cĩ rất nhiều các loại artifact (ECG, EMG…). Hơn nữa việc nhận biết các sĩng nhịp cơ bản cũng khơng đơn giản, dễ dàng do các nhịp này xuất hiện phụ thuộc vào tuổi, vào trạng thái tinh thần của bệnh nhân. Song chúng ta cĩ thể khắc Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 8 - phục được khĩ khăn này bằng việc gửi tín hiệu điện não EEG từ một nơi khơng đáng tin cậy đến những nơi tin cậy mà ở đĩ cĩ những bác sĩ giỏi, kinh nghiệm thực hiện việc đọc bản ghi và chẩn đốn lâm sàng. Từ đây phát sinh một yêu cầu cần thiết là thực hiện truyền hiệu quả tín hiệu EEG cả về mặt vật lý lẫn hiệu quả kinh tế. Do đĩ thực hiện nén EEG là cần thiết. Hơn nữa thực hiện cơng việc này cũng sẽ giúp ích rất nhiều trong việc nghiên cứu về tín hiệu EEG như việc loại bỏ artifacts, dị tìm xung động kinh, và phân loại các dạng xung này bằng việc gửi bản ghi điện não từ bệnh viện đến nơi thực hiện nghiên cứu. Trước tiên nén là để giảm thời gian truyền, giảm khơng gian lưu trữ, và trong những hệ thống xách tay, nĩ giảm yêu cầu bộ nhớ hay tăng số lượng kênh và dải thơng. Một trong những mục đích đầu tiên của việc làm này là tự động thu thập những dữ liệu EEG mà được yêu cầu với những đặc tính hạn chế từ trước ( luồng dữ liệu 20 480 bps) từ bệnh viện ngoại vi hay từ nhà bệnh nhân, mà truyền qua mơi trường truyền tốc độ thấp như là đường dây điện thoại đĩng mạch hay mạng điện thoại tế bào, với những phần cứng giá rẻ, mà khơng nhất thiết phải cĩ mặt của bác sĩ. Những thuật tốn nén dữ liệu cho phép người bệnh thực thi một hệ thống xách tay để gửi tín hiệu EEG (20 kênh, 128 Hz, 8-b), trong thời gian thực qua đường điện thoại với modem 14 400 bps. Một y tá trực thu tín hiệu và trong quá trình thu, bác sĩ chỉ cần liên lạc với y tá qua điện thoại. Vì vậy, bệnh nhân khơng cần gặp trực tiếp bác sỹ điều trị nữa. Dữ liệu được thu thập từ nơi bệnh nhân nằm và sau đĩ kết quả chẩn đốn, phương pháp điều trị sẽ được gửi trở lại. Điều này cũng dẫn đến việc giảm giá tồn bộ, khi việc chuyên chở bệnh nhân là khơng cần nữa. Một động lực khác để nén dữ liệu là đối với nhiều trường hợp ở đĩ lượng dữ liệu được lưu trữ vượt quá khả năng của các thiêt bị lưu trữ thương mại. Trong trường hợp này, giá cả và những giới hạn về cơng nghệ của những thiết bị lưu trữ khối cĩ sẵn bắt buộc chúng ta phải giảm tốc độ lấy mẫu từ 128 tới 64 Hz và số lượng kênh ghi từ 20 kênh xuống 12 kênh, tuy nhiên chất lượng tín hiệu vẫn cĩ thể chấp nhận được, vì vậy những kĩ thuật nén dữ liệu EEG rất hữu ích và đạt hiệu quả thương mại cao . Bộ vi xử lý mà giám sát thiết bị thu EEG cĩ thể được dành cho nén dữ liệu chỉ trong một phần nhỏ thời gian giữa 2 mẫu tín hiệu vào liên tiếp. Chiều dài từ mà mã được tạo ra từ những thuật tốn nén cĩ thể là rất dài (những tín hiệu xảy ra hiếm khi), khiến mất dữ liệu do khả năng tính tốn giới hạn của bộ vi xử lý. Để đối phĩ với bộ biến đổi A/D tốc độ dữ liệu và yêu cầu tính tốn thấp, một kĩ thuật nén dựa vào chiều dài từ mã lớn nhất cố định được chấp nhận. Từ sự cần thiết đĩ, mục tiêu của đề tài này là nghiên cứu một vài thuật tốn để tìm ra được phương pháp nén EEG hiệu quả nhất dựa trên một yêu cầu và tiêu chí đánh giá nào đĩ. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 9 - CHƯƠNG 2: LÝ THUYẾT NÉN DỮ LIỆU 2.1. Những vấn đề chung Mã chiều dài thay đổi là mã được mong muốn cho việc nén dữ liệu vì chúng ta cĩ thể đạt được việc tiết kiệm tồn cục bằng cách gán những từ mã ngắn cho những kí tự xuất hiện thường xuyên và những từ mã dài hơn cho những kí tự xuất hiện ít hơn. Ví dụ, cho mã chiều dài thay đổi (0, 100, 101, 110, 111) với chiều dài từ mã (1, 3, 3, 3, 3) cho bảng kí tự (A, B, C, D, E), và chuỗi kí tự nguồn là BAAAAAAAC với tần suất của mỗi kí tự là (7, 1, 1, 0, 0). Khi đĩ lượng bít trung bình được yêu cầu là: (2.1) Việc này đã tiết kiệm được gần một nửa số bit so với việc biểu diễn bằng mã chiều dài cố định 3 bits/symbol Một nguồn được mơ hình hố bằng một bảng S = (s1, s2, …, sn) và sự phân phối xác suất tương ứng là P = (p1, p2,…,pn) Giả sử chúng ta xuât phát từ mã C =(c1, c2, …, cn) với chiều dài mỗi từ mã là L = (l1, l2,…, ln). Hình 11 : Code and source data Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 10 - Mục tiêu của chúng ta là cực tiểu hố chiều dài trung bình của từ mã : (2.2) Do vậy mã chiều dài thay đổi rất hữu ích cho việc nén dữ liệu. Tuy nhiên, một mã chiều dài thay đổi sẽ trở nên vơ giá trị nếu như khơng thể nhận ra một cách duy nhất những từ mã của mã này từ bản tin đã được mã hố Ví dụ : Cho mã chiều dài thay đổi (0, 10, 010, 101) của bảng kí tự (A, B, C, D) . Một đoạn tin là ‘0100101010’ cĩ thể được giải mã nhiều hơn một cách. Ví dụ ‘0100101010’ cĩ thể dịch là ‘ 0 10 010 101 0’ là ‘ ABCDA’ hoặc ‘010 0 101 010 ‘ là CADC. Khi đĩ sẽ khơng nhận được chính xác dữ liệu nguồn Một mã được coi là cĩ khả năng giải mã duy nhất nếu cĩ duy nhất một cách cĩ thể để giải mã bản tin mã hố. Một giải pháp dường như khả quan cho những trường hợp mã khơng phải là mã cĩ khả năng giải mã duy nhất đĩ là thêm vào những kí tự phân cách mở rộng trong giai đoạn mã hố. Ví dụ, chúng ta sử dụng kí tự ‘/’, sau đĩ mã hố chuối kí tự ABCDA là ‘0/10/010/101/0’. Tuy nhiên, phương pháp này phải trả giá quá đắt bởi vì kí tự mở rộng ‘/’ phải được chèn vào cho mỗi từ mã. Mã lý tưởng trong trường hợp này là một mã mà khơng chỉ cĩ chiều dài thay đổi mà cịn cĩ đặc tính tự phân cách. Một loại được gọi là mã tiền tố (prefix code) là mã như thế. “Tiền tố” là một vài bit đầu tiên của một từ mã. Khi hai từ mã cĩ chiều dài khác nhau, cĩ thể từ mã ngắn hơn sẽ giống hệt với vài bít đầu tiên của từ mã dài hơn. Một mã tiền tố (prefix code) là mã trong đĩ khơng từ mã nào là tiền tố của từ mã nào, hay cũng khơng thể một từ mã mà xuất phát từ một từ mã khác bằng cách cộng thêm vào sau vài bit từ từ mã ngắn hơn. Hình 12 : A Prefix code Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 11 - Những mã tiền tố chỉ là một tập con của mã khả năng giải mã duy nhất. Nên nếu một mã khơng phải là mã tiền tố thì chúng ta khơng thể khẳng định rằng từ mã này khơng thể giải mã một cách duy nhất. Ví dụ : mã (0, 01, 011, 0111) cho (A, B, C, D). Rõ ràng đây khơng phải là mã tiền tố vì từ mã này là tiền tố của từ mã kia. Song nếu nhận được một bản tin mã hố 01011010111, thì chỉ cĩ một cách giải mã duy nhất là 01 011 01 0111 đĩ là BCBD. Một số mã cĩ khả năng giải mã duy nhất nhưng yêu cầu phải xem xét ngay từ đầu trong suốt quá trình giải mã. Điều này khiến chúng khơng hiệu quả bằng mã tiền tố (prefix codes) 2.2. Lý thuyết thơng tin 2.2.1. Khái niệm thơng tin Thơng tin là những tính chất xác định của vật chất mà con người (hoặc hệ thống kĩ thuật) nhận được từ thế giới vật chất bên ngồi hoặc từ những quá trình xảy ra trong bản thân nĩ. Về mặt thơng kê người ta đưa ra một số khái niệm về thơng tin như sau:  Điều gì đã xác định (khẳng định được, đốn chắc được, khơng bấp bênh,…) thì khơng cĩ thơng tin và người ta nĩi rằng lượng thơng tin chứa trong điều ấy bằng khơng  Điều gì khơng xác định (bất định) thì điều đĩ cĩ thơng tin và lượng thơng tin chứa trong nĩ khác khơng. Nếu ta càng khơng thể ngờ tới điều ấy thì thơng tin điều đĩ mang lại cho ta càng lớn Tĩm lại, ta nhận thấy khái niệm thơng tin gắn liền với sự bất định của đối tượng ta cần xét. Cĩ sự bất định về một đối tượng nào đĩ thì những thơng báo về đối tượng đĩ sẽ cho ta thơng tin. Khi khơng cĩ sự bất định thì sẽ khơng cĩ thơng tin về đối tượng đĩ. Như vậy, khái niệm thơng tin chỉ là một cách diễn đạt khác đi của khái niệm sự bất định. Trước khi nhận tin (được thơng báo) về một đối tượng nào đấy thì vẫn cịn sự bất định về đối tượng đĩ, tức là độ bất định về đối tượng đĩ khác khơng (cĩ thể lớn hay nhỏ). Sau khi nhận tin (đã được hiểu rõ hoặc hiểu một phần) về đối tượng thì độ bất định của nĩ giảm đến mức thấp nhất, hoặc hồn tồn mất. Như vậy, “ thơng tin là độ bất định đã bị thủ tiêu” hay nĩi một cách khác “ làm giảm độ bất định kết quả cho ta thơng tin” Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 12 - 2.2.2. Lượng thơng tin 2.2.2.1. Định nghĩa lượng thơng tin Như chúng ta đã biết : trước khi nhận tin thì độ bất định lớn nhất, sau khi nhận tin (hiểu rõ hoặc hiểu một phần về đối tượng thì độ bất định giảm đến mức thấp nhất), cĩ khi triệt tiêu hồn tồn. Như vậy, cĩ một sự chệnh lệch giữa độ bất định trước khi nhận tin và độ bất định sau khi nhận tin. Sự chênh lệch đĩ là mức độ thủ tiêu độ bất định. Độ lớn, nhỏ của thơng tin mang đến cho ta phụ thuộc trực tiếp vào mức độ lệch đĩ. Vậy : “Lượng thơng tin là mức độ bị thủ tiêu của độ bất định  Lượng thơng tin = độ chêch của độ bất định trước và sau khi nhận tin = độ bất định trước khi nhận tin - độ bất định sau khi nhận tin (độ bất định tiên nghiệm - độ bất định hậu nghiệm) “. 2.2.2.2.Giới thiệu về lý thuyết thơng tin Mặc dù những kiến thức về đo lượng thơng tin đã được sử dụng một thời gian, song người đã gom gĩp tất cả mọi thứ lại thành một lĩnh vực được gọi là lý thuyết thơng tin (information theory) là Claude Elwood Shannon, một kĩ sư điện ở phịng thí nghiệm Bell. Shannon đã định nghĩa một đại lượng gọi là lượng thơng tin (self- information). Giả sử chúng ta cĩ một sự kiện A, là tập hợp của các kết cục của một thí nghiệm ngẫu nhiên nào đĩ. Nếu sự kiện A xảy ra với xác suất là P(A), thì lượng thơng tin của A được cho bởi i(A) = logb )( 1 AP = - logb P(A) (2.3) Chú ý rằng chúng ta khơng chỉ cụ thể cơ số của hàm log. Chúng ta sẽ thảo luận sau về vấn đề chi tiết hơn. Sử dụng hàm log để đo thơng tin khơng phải là sự lựa chọn tuỳ ý. Nhớ lại rằng log(1) = 0, và –log(x) tăng khi x giảm từ 0 đến 1. Vì vậy, nếu xác suất của một sự kiện là thấp, thì lượng thơng tin của nĩ là cao; nếu xác suất của một sự kiện là cao, lượng thơng tin tương ứng là thấp. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 13 - Hình 13: self-information Một tính chất khác của định nghĩa tốn học về thơng tin là lượng thơng tin thu được từ sự xảy ra của hai sự kiện độc lập là tổng lượng thơng tin thu được từ sự xảy ra của mỗi sự kiện riêng lẻ. Giả sử rằng A và B là hai sự kiện độc lập. Lượng thơng tin tương ứng của sự xảy ra của cả sự kiện A và B là i(AB) =logb )( 1 ABP (2.4) Khi A và B là độc lập thì ta cĩ : P(AB) = P(A)P(B) (2.5) Và do đĩ i(AB) = logb )()( 1 BPAP = logb )( 1 AP + logb )( 1 BP = i(A) + i(B) (2.6) Đơn vị thơng tin phụ thuộc vào cơ số của hàm log. Nếu chúng ta sử dụng cơ số 2, thì đơn vị là bits, nếu sử dụng cơ số e, đơn vị là nats; và nếu sử dụng cĩ số 10, thì đơn vị là hartleys. Lưu ý rằng tính tốn thơng tin bằng bits, chúng ta cần phải lấy logarithm cơ số 2 của xác suất. Bởi vì hàm này khơng xuất hiện trong máy tính, nên ta phải thực hiện như sau : Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 14 - Ta cĩ : logbx = a Suy ra : ba = x Vì vậy nếu ta muốn lấy log cơ số 2 của x Log2x = a => 2a = x, Chúng ta muốn tìm giá trị của a. Chúng ta cĩ thể lấy hàm log tự nhiên (log cơ số e) hay log cơ số 10 cả 2 vế (2 hàm này cĩ xuất hiện trong máy tính). Thì Ln(2a) = lnx => aln2 = lnx Và a = 2ln ln x (2.7) Nếu chúng ta cĩ một tập hợp những sự kiện độc lập Ai, là những tập hợp của các kết cục của thí nghiệm S cĩ nghĩa là UAi = S Ở đây S là khơng gian mẫu, khi đĩ lượng thơng tin trung bình của thí nghiệm ngẫu nhiên được cho bởi cơng thức : H =  P(Ai)i(Ai) = - P(Ai)logbP(Ai). (2.8) Đại lượng này được gọi là entropy của thí nghiệm. Một trong những đĩng gĩp của Shannon là ơng đã chỉ ra rằng nếu thí nghiệm là một nguồn bao gồm những kí tự Ai, từ tập hợp A, thì entropy là đại lượng đo số lượng kí tự nhị phân trung bình cần để mã hố lối ra của nguồn. Shanno đã chứng minh rằng một sơ đồ nén khơng mất thơng tin tốt nhất (lossless compression) là cĩ thể thực hiện được nén lối ra nguồn với lượng bit trung bình bằng với entropy của nguồn. Tập hợp những kí tự A thường được gọi là bảng chữ của nguồn, và những kí tự được gọi là những chữ cái. Đối với một nguồn S tổng quát với bảng chữ A = {1, 2,…, m} mà tạo ra một chuỗi {X1, X2, …}, thì entropy được cho bởi H(S) = n lim Gn n 1 (2.9) Ở đây Gn =          mi i mi i min in nn iXiXiXP 1 11 2 12 1 2211 log),....,,(..... P(X1=i1,X2=i2,…, Xn=in) (2.10) Và (X1, X2, …, Xn) là một chuỗi chiều dài n từ nguồn. Nếu mỗi thành phần trong chuỗi là phân phối độc lập đồng nhất (independent and identically distributed (iid)) , thì chúng ta cho cĩ chứng minh rằng Gn = -n     mi i iXPiXP 1 1 1 1111 )(log)( Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 15 - Và phương trình entropy trở thành H(S) = -  )(log)( 11 XPXP (2.11) Đối với đa số các nguồn phương trình (2.9) và (2.11) là khơng đồng nhất. Nếu chúng ta cần phải phân biệt giữa hai phương trình đĩ, thì chúng ta sẽ gọi đại lượng được tính tốn theo phưong trình (2.11) là entropy bậc nhất (first-order entropy) của nguồn, trong khi đại lượng theo phương trình (2.9) được gọi là entropy của nguồn Thơng thường khơng thể biết được entropy đối với một nguồn vật lý.Vì thế chúng ta phải ước lượng entropy. Việc ước lượng entropy phụ thuộc vào giả thiết của chúng ta về cấu trúc của chuỗi nguồn. 2.3. Các phương pháp nén dữ liệu 2.3.1. Các phương pháp nén khơng mất thơng tin 2.3.1.1 Mã Huffman Một thuật tốn mã hố rất phổ biến là thuật tốn mã hố Huffman. Đầu tiên chúng ta sẽ trình bày một thủ tục để xây dựng mã Huffman khi biết được mơ hình xác suất cho nguồn, sau đĩ một thủ tục giành cho việc xây dựng mã khi khơng biết được số liệu thống kê của nguồn. Kĩ thuật này được phát triển bởi David Huffman. Mã được tạo ra bằng cách sử dụng kĩ thuật này hay thủ tục này được gọi là mã Huffman. Những mã này là những mã prefix và là mã tối ưu đối với mơ hình đã cho (tập hợp xác suất). Thủ tục Huffman được dựa trên hai quan sát đối với mã tiền tố tối ưu. 1. Trong một mã tối ưu, những kí tự mà xảy ra thường xuyên hơn ( cĩ xác suất xảy ra cao hơn) sẽ cĩ từ mã ngắn hơn những kí tự mà xảy ra ít hơn 2. Trong một mã tối ưu, hai kí tự mà tần xuất xảy ra thấp nhất sẽ cĩ cùng chiều dài. Chúng ta dễ dàng nhận ra rằng quan sát đầu tiên là đúng. Nếu những kí tự mà xảy ra thường xuyên hơn cĩ từ mã dài hơn từ mã của những kí tự xảy ra ít thường xuyên hơn, thì số lượng bit trung bình trên mỗi kí tự sẽ lớn hơn nếu trường hợp ngược lại. Vì vậy, một mã gán những từ mã dài hơn cho những kí tự xảy ra thường xuyên khơng thể tối ưu Chúng ta hãy xem xét tại sao quan sát thứ hai đúng, xét trường hợp sau. Giả sử tồn tại một mã tối ưu C trong đĩ hai từ mã tương ứng với hai kí tự xác suất thấp nhất khơng cĩ chiều dài giống nhau. Giả sử từ mã dài hơn dài hơn k bits so với từ mã ngắn Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 16 - hơn. Do đây là mã prefix, nên từ mã ngắn hơn khơng thể là tiền tố của từ mã dài hơn. Điều này cĩ nghĩa là thậm chí nếu chúng ta để k bits rơi vào k vị trí cuối cùng của từ mã dài hơn, thì hai từ mã này vẫn hồn tồn khác biệt. Do những từ mã này tương ứng với những kí tự xác suất thấp nhất trong bảng kí tự, nên sẽ khơng cĩ một từ mã nào khác cĩ thể dài hơn những từ mã này; vì vậy, sẽ khơng cĩ nguy cơ là từ mã ngắn hơn sẽ trở thành tiền tố của từ mã khác nào đĩ. Hơn nữa, cắt bỏ k bit này chúng ta sẽ thu được một từ mã mới cĩ chiều dài trung bình ngắn hơn C . Nhưng điều này vi phạm đến luận điểm ban đầu của chúng ta là C là một mã tối ưu. Vì vậy đối với một mã tối ưu quan sát thứ hai là đúng. Thu được thủ tục mã Huffman bằng cách bổ sung một yêu cầu đơn giản đối với hai quan sát này. Yêu cầu này là những từ mã tương ứng với hai kí tự cĩ xác suất thấp nhất chỉ khác nhau ở bit cuối cùng. Cĩ nghĩa là, nếu  và  là hai kí tự xác suất thấp nhất trong bảng kí tự, nếu từ mã của  là m*0, thì từ mã của  sẽ là m*1. Ở đây m là một chuỗi bit 0 và 1, và * biểu thị sự mĩc nối vào nhau. Yêu cầu này khơng vi phạm hai quan sát của chúng ta và dẫn đến một thủ tục mã hố rất đơn giản. Chiều dài trung bình của một mã là : L =  )()( ii acaP (2.12) Trong đĩ P(ai) là xác suất của kí tự ai cịn c(ai) là từ mã tương ứng. Đo hiệu quả của mã này là dư thừa của nĩ – đĩ là sự khác nhau giữa entropy và chiều dài trung bình. Thủ tục này sẽ được minh hoạ bằng ví dụ sau: Huffman code for the orginal Five-letter alphabel Letter Probability Codeword a2 0.4 1 a1 0.2 01 a3 0.2 000 a4 0.1 0010 a5 0.1 0011 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 17 - Huffman Tree (0.4) (0.4) (0.6) 0 a2(0.4) (0.2) (0.4) 0 (0.4) 1 (1.0) a1(0.2) (0.2) 0 (0.2) 1 a3(0.2) a4(0.1) 0 (0.2) a5(0.1) 1 Hình 14: Cây huffman Một cách khác xây dựng mã Huffman sử dụng thực tế là mã Huffman, do ưu điểm của mã tiền tố, cĩ thể biểu diễn là một cây nhị phân trong đĩ những nút ngồi hay lá ngồi sẽ tương ứng với những kí tự. Mã Huffman này đối với bất kì kí tự nào cĩ thể thu được bằng cách di chuyển trên cây từ nút gốc đến lá tương ứng với kí tự, cộng bit 0 tới từ mã mỗi lần chúng ta đi qua một cành cao hơn, và bit 1 mỗi lần đ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ụ : Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 18 - 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 : Như vậy bộ mã tối ưu tương ứng là : A B C D E 010 011 11 00 10 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 19 - 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ã hố 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ã hố (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 tố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ã hố số học (arithmetic coding technique) sẽ thực hiện được yêu cầu này. Trong mã hố 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ã hố. 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 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 20 - 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), Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 21 - 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ư Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 22 - 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 hồ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 hồn tồ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 tồ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 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 23 - 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 hồn tồ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ã hố 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ã hố 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 hồn tồ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 đĩ đốn mỗi chữ cái. Nếu người đĩ đốn đúng, nĩi cơ ấy đúng và Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 24 - chuyển sang chữ cái tiếp theo. Nếu cơ ấy đố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 đố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 đố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 đố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 khố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 tố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 đố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 đốn cho đến khi cơ ấy đốn được chữ cái đúng và số lượng đốn cần đến để đốn đúng chữ cái sẽ được ghi nhớ. Hơn nữa, hầu hết những lần đốn đúng, thì kết quả là 1 là số cĩ thể nhất. Sự tồn tại của cặp đơi tố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 đốn là người dự đốn kí tự tiếp theo trong chuỗi tốt hơn nhiều bất kí một bộ dự đốn tố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ự đố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ã hố 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ã hố 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ã hố. Nếu chúng ta biết được ngữ cảnh trong đĩ một kí tự xảy ra chúng ta cĩ thể đố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ự Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 25 - 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ã hố 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ã hố, 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ã hố từ “probability”. Giả sử chúng ta đã mã hố bốn chữ cái đầu tiên và muốn mã hố 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ã hố sự xảy ra đĩ. Vì vậy chúng ta muốn làm những gì để mã hố 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 khố 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 tố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 = ompressionsizebeforc ompressionsizeafterc (2.18)  Hệ số nén Compression factor = ompressionsizeafterc ompressionsizebeforc (2.19)  Phần trăm tiết kiệm %tiết kiệm = .% ncompressiosizebefore ompressionsizeaftercncompressiosizebefore  (2.20) Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 26 - 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 đốn và điều trị bệnh nhân cĩ rối lọan não. Ví dụ như, chuẩn đố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 tồ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 hồn tồ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 hồn tồ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 tố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 tốn thấp. Bằng cách khai thác kết quả này một sơ đồ mã hố / 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: Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 27 - Hình 16 : data EEG in compression Dữ liệu nguồn (EEG signal) Source binary file Compressed binary file Compression (coding) Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 28 - 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ự đố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 tố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 hồn tồ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 Compressed binary file Reconstructed binary file Decoded data in file (EEG signal) Decompression (decoding) Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 29 - 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 đố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 tố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ự đốn tín hiệu (những bộ dự đố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ự đố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ử hố 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ự đố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. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 30 - 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 tốn cơ bản của một thuật tốn cùng cấu trúc dữ liệu được biểu diễn như sau: ENCODER DECODER Input output 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 tố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 : 00000000 00000001 00000010 00000011 00000100 ………… 1 00 011 1001 110 ……. 00000001 00000010 00000000 0 1 0 1 1 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 31 - H = -   M i ii pp 1 2 )(log (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 - b H (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 tốn tham lam nhằm khai thác cây nhị phân Huffman. Do tỉ lệ nén nén của nĩ rất gần với giới hạn nén được biểu diễn ở (3), mã hĩa Huffman cũng được gọi là mã hĩa entropy. Kĩ thuật này được sử dụng cho phương pháp nén dữ liệu khơng mất thơng tin. Do đĩ ta hồn tồn cĩ thể sử dụng nĩ như là một phương pháp điển hình cho nén tín hiệu EEG. Ở đây chúng ta sử dụng những thuật ngữ “kí tự” (symbol or character), để biểu diễn dữ liệu lối vào cho thuật tốn của chúng ta, đĩ là những mẫu tín hiệu EEG. Việc này hồn tồn chỉ là thuận lợi cho việc mơ tả thuật tốn. Input Bảng chữ A = {a1, a2, …,an} là bảng kí hiệu kích thước n Tập W = {w1, w2, …,wn} là tập hợp những trọng số kí tự (luơn luơn tỉ lệ thuận với xác suất của kí tự), cụ thể wi = weight (ai) , 1  i  n. Output Mã C(A, W) = {c1, c2,…,cn}, là tập hợp những từ mã (mã nhị phân), ở đây ci là từ mã của ai, 1  i  n Mục đích Đặt L(C) =    n i clengthw ii 1 )( là chiều dài tổng cộng của từ mã C. Điều kiện phải đạt được là L(C)  L(T) đối với mọi mã T (A, W). Đây là thuật tốn xây dựng mã Huffman thơng thường dựa vào xác suất đã biết của các mẫu tín hiệu. Tuy nhiên, đối với tín hiệu EEG, nhiều khi cần phải tiến hành ghi tín hiệu điện não trong thời gian dài (long-term signal), và nhiều lúc xuất hiện những tín hiệu bộc phát biểu hiện bệnh lý bất thường cĩ biên độ lớn hơn rất nhiều so với các tín hiệu cơ bản hay các tín hiệu xảy ra hiếm khi. Khi đĩ sử dụng thuật tốn Huffman truyền thống rất cĩ khả năng sẽ tạo ra những từ mã rất dài, mà vượt quá khả Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 32 - năng của các thiết bị lưu trữ thơng thường. Để giải quyết vấn đề này chúng ta sẽ sử dụng một kĩ thuật dựa vào cây Huffman “collapsed” (collapsed Huffman Tree - CHT). Kĩ thuật này cho phép tạo ra một mã mà chứa từ mã cĩ chiều dài cực đại xác định (fixed- maximum length codeword). Trên CHT, mỗi lá sẽ được liên kết với một xâu bit chiều dài thay đổi mà mã hĩa kí tự tương ứng trên lá đĩ và sẽ tồn tại chính xác một lá mà tương ứng với một tập hợp những kí tự thay cho một kí tự duy nhất . Ý tưởng là tạo ra những lá cây co (collapse) để những đường dẫn dài từ gốc (root) được ngắn lại, vì vậy sẽ giới hạn được chiều dài xâu bit cực đại của những từ mã. Cho một bảng kí tự nguồn là A={a1, a2, a3,…., aM} và đặt I ={1, 2, …, M} là tập hợp của những chỉ số của nĩ. Sẽ khơng mất tính tổng quát, khi giả sử những kí tự này được sắp xếp thứ tự theo xác suất của nĩ, cụ thể là , nếu pi là xác suất của ai thì p1>p2>….>pM (3.4) Giả sử rằng A được chia thành hai tập con khơng giao nhau A1 và A2 , với chỉ số tương ứng trong I1, I2. Thuật tốn nén CHT coi A2 như là một kí tự duy nhất s được mã hĩa, với xác suât tương ứng Ps =   2Ii pi (3.5) Xem xét vấn đề thu được sự khơi phục chính xác những mẫu từ kí tự ak thuộc A2, và chia mã tiền tố giống nhau mà được sinh ra cho s cho tất cả các thành phần khác của A2. Trong trường hợp này, theo sau từ mã s là b bít chiều dài cố định, ban đầu của kí tự ak sẽ được phát ra. Trong các bước giải mã, khi chuỗi bit tương ứng với s được tìm ra, thì b bit liên tiếp được dịch như giống như kí tự nguồn. Tỉ lệ nén đạt được bởi kĩ thuật này là : C = 1 - b H - ps (3.6) Ở đây H là entropy của những kí tự A1{s} = {ai1,…., aim, s}. Số hạng ps là xác suất của các kí tự thuộc A2. Sự ép buộc chiều dài từ mã cực đại sẽ được gán vào giá trị được lựa chọn cho m (cụ thể, chủ yếu của A1), vì cây Huffman cuối cùng cĩ m+1 lá, nên số lượng bit của từ mã được tính bằng tổng chiều cao của cây CHT mà dẫn đến lá tương ứng với từ mã đĩ, nếu cần thiết cộng thêm b bit do mã hĩa chuỗi bit nguồn khi lá biểu diễn A2. Vì mã Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 33 - được xem như là sự phân chia A thành hai tập con A1, A2, để thiết kế một mã tối ưu tập hợp chỉ số I1* phải được chọn lựa sao cho (3.7) Khơng may mắn là cĩ thể lựa chọn tập I1 của m chỉ số từ {1, …, M} trong số những cách bằng nhị thức của m trên M. Rõ ràng khơng thể khảo sát tỉ mỉ trong tồn bộ khơng gian tìm kiếm, vì vậy chúng ta lựa chọn để xác định tập I1, I2 bằng kinh nghiệm đơn giản sau: I1 = {1, 2, …., m} I2 = {m+1, …., M} (3.8) Do xác suất được sắp thứ tự, nên sự phân chia này đảm bảo rằng những kí tự cĩ xác suất cao sẽ cĩ từ mã riêng của nĩ, trong khi những kí tự khơng thường xuyên xuất hiện được co lại thành một lá duy nhất của cây Huffman. Khơng loại trừ trường hợp giải pháp này chỉ tương ứng với sự tối ưu cục bộ, bởi hàm được tối thiểu được tổng hợp bởi những số hạng cơ bản mà khơng phải đơn điệu (-xlog2(x) với x Є [0, 1]), để khơng chỉ đơn giản xuất phát từ đáp ứng (behavior) của hàm yêu cầu (7) khi số hạng pi, pj được trao đổi giữa I1, I2. Giả sử cho một bảng kí tự nguồn A= {a, b, c, d, e, f} với xác suất lần lượt là P = {0.4, 0.2, 0.2, 0.1, 0.05, 0.05}. Khi đĩ ta sẽ nhĩm các kí tự thành 2 nhĩm A1, A2 khơng giao nhau như sau : A1 = {a, b, c, d} A2 = {e,f} = s Khi đĩ Ps = (pe + pf) = 0.1 Ta xây dựng mã Huffman cho tập B = {a, b, c, d, s} với xác suất lần lượt là P’ = {0.4, 0.2, 0.2, 0.1, 0.1}. Với mơ hình như trên chúng ta cĩ một mã sắp theo thứ tự của các kí tự như sau : C’ = {0, 10, 110, 1111, 1110}. Và do đĩ mã tương ứng của bảng nguồn là C = {0, 10, 110, 1111, 11100, 11111}. 3.1.1.3. Nén đếm lặp Nếu một file chứa những chuỗi dài những kí tự lặp lại cĩ thể nén nĩ lại, thì chúng ta cĩ thể giảm sự lặp lại những kí tự này bằng phương pháp sử dụng kĩ thuật nén mã chạy loạt (run-length compression techniques). Trong bài báo cáo này này chúng ta sẽ Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 34 - xem xét một biến thể của nén mã chạy loạt, đĩ là phương pháp nén đếm lặp (repetion count compression), ở đĩ mỗi kí tự được theo sau bởi một bộ đếm lặp, mà biểu diễn số lần xảy ra liên tiếp của kí tự đĩ. Ví dụ như sau: Cho một chuỗi AAAAAAAABBBCAAAACCCB. Sử dụng kĩ thuật mã đếm lặp ta mã hĩa chuỗi kí tự kia như sau : 8A3BC4A3CB. ‘8A’ cĩ nghĩa là ‘tám chữ A’. Bộ đếm đã đếm số lần lặp lại liên tiếp của các kí tự, sau đĩ thay những kí tự lặp lại bằng số lần lặp lại của nĩ. Kĩ thuật này rất ích lợi khi tồn bộ chi phí được đưa vào cho những bits bộ đếm sẽ được đền bù bằng việc loại bỏ những kí tự lặp lại. Đối với luồng dữ liệu được nén đếm lặp mã Huffman được áp dụng để giảm hơn nữa. Tuy nhiên, tồn bộ quá trình khơng đạt được tỉ lệ cao hơn so với mã hố entropy dữ liệu nguồn. Cụ thể hơn, nếu H là entropy của nguồn và N là số lượng mẫu, L = NH sẽ là chiều dài file được tạo bởi mã hố entropy. Nếu sử dụng bộ đếm lặp, số lượng kí tự lưu trữ ở file nén được giảm đi: N / (R + 1) (3.8) ở đây R là giá trị trung bình bộ đếm lặp. Trong trường hợp như thế, số bit bộ đếm lặp (gọi là B) sẽ làm tăng số lượng bit trên mỗi kí tự. và chiều dài file được tạo bởi phương pháp nén đếm lặp là: L’ = N(H + B) / (R + 1) (3.9) Với giả thiết rằng entropy của các kí tự khơng thay đổi, đây là một giả thuyết tối ưu bởi thơng thường entropy được xem như là tăng khi những kí tự lặp lại bị xố bỏ từ luồng dữ liệu. Vì thế, L’ được coi như là tăng đối với giá trị xấp xỉ này. Đạt được sự cải thiện hiệu quả nén yêu cầu L’ < L. Khi đĩ : H R > B (3.10) Cĩ nghĩa rằng, lợi ích của phương pháp nén này đạt được khi mã hố Huffman của những kí tự lặp lớn hơn số bit yêu cầu để biểu diễn bộ đếm lặp. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 35 - 3.1.1.4. Kĩ thuật nén dự đốn (preditive compression techniques) Hình 19 biểu diễn một sơ đồ để thực hiện phép biến đổi ngược được sử dụng rộng rãi để giảm bớt entropy của tín hiệu : entropy của tín hiệu biến đổi càng thấp thì tỉ lệ nén đạt được càng cao. Thực hiện việc dự đốn một mẫu tín hiệu dựa vào vài giá trị mẫu quá khứ là nhiệm vụ của một khối được gọi là bộ dự đốn, và sai số (error) giữa giá trị thực và giá trị dự đốn được mã hố bằng mã chiều dài thay đổi (e.g … mã Huffman). Hình 19: sự truyền tín hiệu dựa vào sơ đồ dự đốn Sai số này được biểu diễn bởi hiệu sau : en = xn – f (xn-1,…, xn-N) (3.11) ở đĩ xn là mẫu vào thứ n (viết tắt của x(nT) với 1/T là tốc độ lấy mẫu) và en là sự khác nhau giữa mẫu vào và mẫu dự đốn Nếu dự đốn chính xác tại hầu hết mọi thời điểm thì lỗi dự đốn sẽ càng gần khơng, và vì vậy cĩ thể sử dụng chuỗi bit ngắn để mã hố sai số này và những chuỗi bit dài hơn để mã hố giá trị en khác. Ba loại bộ dự đốn sẽ được xem xét. Đĩ là những loại dựa vào chuỗi Markov (Markov chains), lọc số (digital filtering), dự đốn tuyến tính thích nghi (adaptive linear prediction). 3.1.1.4.1. Bộ dự đốn Markov Trong tốn học, một chuỗi Markov, được đặt theo tên của nhà tốn học người Nga Andrey Markov, là một quá trình ngẫu nhiên với tính chất Markov. Cĩ tính chất Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 36 - Markov cĩ nghĩa là, cho trước trạng thái hiện tại, trạng thái tương lai là độc lập với trạng thái quá khứ. Nĩi cách khác, sự mơ tả trạng thái hiện tại nắm bắt đầy đủ tất cả mọi thơng tin mà cĩ thể ảnh hưởng đến tiến trình tương lai của quá trình. Tiến đến trạng thái tương lai thơng qua quá trình xác suất thay cho quá trình tất định. Tức là, biết hiện tại, khơng bất cứ điều gì đã xảy ra trong quá khứ cĩ thể ảnh hưởng hay xác định kết cục trong tương lai, tương lai là tất cả mọi điều cĩ thể. Về mặt tốn học, quá trình Markov được biểu diễn cho bất kì giá trị n và t1 < t2 < t3, P(x (tn)  xn / x(t)  t  tn-1) = P(x(tn)  xn / x(tn-1)) (3.11) Thơng thường, thuật ngữ chuỗi Markov (Markov chain) được sử dụng để nĩi đến một quá trình Markov thời gian rời rạc. Chuỗi Markov là một chuỗi các biến ngẫu nhiên X1, X2, X3, ... cĩ tính chất Markov. Ta cĩ cơng thức : Pr(Xn+1 = x|Xn = xn, …, X1 = x1) = Pr(Xn+1 = x|Xn = xn) (3.12) Những giá trị cĩ thể của Xi hình thành tập cĩ thể đếm S được gọi là khơng gian trạng thái của chuỗi. Cho chuỗi {xn}. Chuỗi này được gọi là theo mơ hình Markov bậc k nếu : P(xn / xn-1,…,xn-k) = P(xn / xn-1, …, xn-k,..) (3.13) Nĩi cách khác, biết về k mẫu quá khứ cũng là biết về tồn bộ lịch sử quá khứ của quá trình. Nếu kích thước của bảng nguồn là l, thì số trạng thái là lk. Mơ hình Markov được sử dụng phổ biến nhất là mơ hình Markov bậc nhất, khi đĩ P(xn / xn-1) = P(xn / xn-1, xn-2, xn-3,…) (3.14) Phưong trình (3.13) và (3.14) biểu thị sự tồn tại sự phụ thuộc giữa các mẫu. Tuy nhiên, chúng khơng mơ tả dạng phụ thuộc. Chúng ta cĩ thể phát triển những mơ hình Markov bậc nhất (first-order Markov) khác nhau tuỳ thuộc vào giả thiết của chúng ta dạng phụ thuộc giữa các mẫu Bộ dự đốn được biểu diễn bằng hình 19 cĩ thể được thực thi dưới giả thiết là tín hiệu cĩ tính chất Markov và được tạo bởi một nguồn được mơ hình là một chuỗi Markov. Một chuỗi Markov bậc nhất được sử dụng để mơ hình tín hiệu; nĩ yêu cầu ước lượng tất cả mọi xác suất điều kiện P[Xn = ai / Xn-1 = aj], ở đĩ Xn là một biến ngẫu nhiên rời rạc lấy những giá trị trên bảng chữ hữu hạn A = {a1, …, aM}. Những xác suất này cĩ thể được xấp xỉ với tần suất nếu cĩ sẵn một tập huấn luyện đủ lớn. Một ma trận tần suất, mà những thành phần của nĩ Fij đếm sự xảy ra Xn = ai khi Xn-1 = aj, được xuất Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 37 - phát từ một tập huấn luyện (training set) bao gồm 96 mẫu EEG; một tập kiểm tra khác cũng bao gồm 58 mẫu EEG được sử dụng để đánh giá. Ma trận Fij tương đương với sự phân bố xác suất kết hợp của Xn và Xn-1 và được sử dụng trong (3.15) để ước lượng xác suất điều kiện ij = P[Xn = ai / Xn-1 = aj]  ij  k Fij Fij (3.15) Sau đây sẽ ước lượng cho kí tự kế tiếp của kí tự aj bằng cách sử dụng phương pháp tối thiểu hố sai số bình phương trung bình Succ (aj) =   k kj k với  aj  A (12) (3.16) Do dữ liệu được lượng tử bằng 8 b, sẽ cĩ 256 kí tự tạo ra một ma trận tần suất 256256; bằng chứng thực nghiệm đã chứng tỏ rằng : trên tập kiểm tra, sự khác nhau giữa ma trận đơn vị (identity function)và những kí tự kế tiếp cĩ thể nhất của các kí tự 0….255, được tính tốn theo như (3.16) thuộc khoảng từ -3 tới +3, biểu thị rằng ước lượng Markov (Markovian estimate) nhìn chung rất gần với ma trận đơn vị (identity function) 3.1.1.4.2 Bộ dự đốn lọc số Cĩ thể thiết kế một bộ lọc dự đốn tuyến tính số cho tín hiệu EEG và cĩ thể sử dụng nĩ theo như sơ đồ dự đốn hình 19. Hãy xem xét bộ lọc số được mơ tả bằng phương trình sai phân en = xn – b1xn-1 – b2xn-2 - … - bNxn-N (3.17) Trong đĩ bộ dự đốn ở hình 19 được biểu diễn bằng phương trình sau sử dụng một tập hợp các hệ số giống như {b1…bN} yn = b1xn-1 + b2xn-2 + … + bNxn-N (3.18) Cĩ thể thu được tín hiệu lỗi (error signal) entropy thấp en bằng cách tối thiểu hĩa sai số bình phương tổng: E =  n ne2 (3.19) Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 38 - Với quy ước sau :  b t = [b1…bN] _ x t = [xn-1…xn-N] (3.20) Bộ dự đốn tuyến tính sai số bình phương trung bình tối thiểu của dạng  x =  b t .  x được cho bởi nghiệm  b của phưong trình  b t .  Rx = E[xn  x t] (3.21) ở đĩ  Rx là ma trận tương quan của quá trình xn. Thực tế, hàm tự tương quan thật khơng biết được và thu được sự ước lượng từ việc sử dụng một tập hợp các mẫu. 3.1.1.4.3. Dự đốn tuyến tính thích nghi Hai bộ dự đốn tuyến tính thích nghi là bộ dự đốn tuyến tính thích nghi dấu (the sign adaptive linear predictor) và bộ dự đốn tuyến tính thích nghi bình phương trung bình tối thiểu (the least mean square adaptive linear predictor) Những hệ số bộ dự đốn ở (3.18) cĩ thể được xem như những hàm phụ thuộc thời gian, cĩ khả năng thích nghi với những hành vi của tín hiệu (signal behavior). Thuật tốn bình phương trung bình tối thiểu sẽ cập nhật những hệ số bộ dự đốn theo phương trình bi(n) = bi(n-1) + xn-1en (3.22) ở đây trọng số  là tốc độ thích nghi, và en là sai số dự đốn tại thời điểm n Những hệ số bộ dự đốn trong thuật tốn thích nghi dấu được cập nhật theo phương trình: bi(n) = bi(n-1) + xn-1sgn (en) (3.23) ở đây trọng số  là tốc độ thích nghi, và sgn (en) lấy giá trị +1 hay -1 tuỳ theo dấu sai số dự đốn. Tuy nhiên việc lựa chọn giá trị  và  phải cĩ giới hạn vì: trong khi lựa chọn giá trị thấp sẽ dẫn tới việc thích nghi khơng đủ, cịn lựa chọn giá trị cao cĩ thể khiến cho hệ thống khơng ổn định. Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 39 - 3.1.1.4. Phương pháp nén biến đổi (Transformation compression) Một chuỗi N mẫu tín hiệu cĩ thể được xem như là một điểm X trong khơng gian N chiều. Cĩ thể biểu diễn X hiệu quả hơn bằng cách áp dụng một phép biến đổi trực giao Y = TX, ở đây Y biểu thị vectơ biến đổi và T biểu thị ma trận biến đổi. Mục tiêu là lựa chọn một chuỗi con của Y gồm M thành phần, ở đĩ M nhỏ hơn N (vẫn cịn (N- M) thành phần bị loại bỏ) dẫn đến nén. Bằng cách mã hố Huffman sự khác nhau giữa tín hiệu nguồn và tín hiệu được khơi phục từ M thành phần kia, thì những kĩ thuật này lại trở thành mã hố khơng mất thơng tin, bởi vì cĩ thể khơi phục lại chính xác từ M thành phần và sự sai khác đĩ. Cĩ thể chứng minh được rằng biến đổi Karhunen-Loeve (KLT) là phương pháp tối ưu để biểu diễn tín hiệu về giới hạn sai số bình phương trung bình. Nhược điểm chính trong việc sử dụng KLT là thời gian tính tốn đáng kể. Phép biến đổi cosin rời rạc (the discrete cosine transform (DCT)), với tính chất nén năng lượng mạnh cĩ nghĩa là: hầu hết mọi thơng tin tín hiệu đều hướng đến tập trung tại một vài thành phần tần số thấp của DCT, là giải pháp kề tối ưu với sự thuận lợi hơn về tính tốn, thực tế, cĩ tồn tại thuật tốn nhanh. Phép biến đổi này cho những vectơ lối vào thực đã trở nên rất đáng được quan tâm trong mục đích sử dụng để nén tín hiệu EEG. Hình 20: Phổ EEG trung bình khi được tính bởi DCT. Đỉnh 10 Hz là do tín hiệu alpha, và đỉnh 50 Hz là đỉnh của dịng điện nguồn Hình 20 biểu diễn phổ trung bình EEG được tính bởi DCT trên tồn bộ . Một số lượng đáng kể các cơng suất phổ được định vị tại những tần số thấp, tuy nhiên mức độ giảm phổ khơng cao. Vì vậy, tỉ lệ nén dựa vào DCT khơng được mong đợi là cao do Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 40 - những thành phần bị loại bỏ cĩ thể phát sinh ra những lỗi nghiêm trọng. Một điều cần phải chú ý là đỉnh phổ tại vị trí 10 Hz, tương ứng những dạng sĩng EEG quan trọng nhất, sĩng alpha, thuộc phạm vi từ 8 đến 13 Hz. Một đỉnh thứ hai tại 50 Hz biểu diễn nhiễu mạng điện lưới và luơn được loại bỏ bởi bộ lọc North số trước khi cĩ thể nhìn thấy. Do những thành phần quan trọng về mặt sinh học nằm dưới 20 Hz, tương ứng với 50 của 256 thành phần, nên 50 thành phần DCT đầu tiên sẽ được giữ lại trong quá trình nén. 3.1.2. Giới thiệu các phương pháp nén EEG khác 3.2. Những đặc trưng của tín hiệu EEG Những phương pháp được trình bày ở trên gần như khơng sử dụng những thơng tin về EEG. Một điều chắc chắn rằng sử dụng những thơng tin phụ thuộc miền của tín hiệu cực kì quan trọng và nĩ sẽ cung cấp một chiến lược nén tốt nhất. Tín hiệu EEG cĩ sự tương quan về khơng gian và cả thời gian mà ta cĩ thể khai thác để thiết kế những chiến lược nén hiệu quả. Về sự tương quan khơng gian, vài kĩ thuật cĩ thể sử dụng là lượng tử hố vectơ (vector quantization) và phân tích chuỗi thời gian đa biến. Chúng ta cĩ thể khai thác kĩ thuật lượng tử hố vector bằng cách ánh xạ một vectơ bao gồm những mẫu kênh lối vào tới một vectơ mã, và mã hố cùng với vectơ lỗi. Sự tương quan thời gian được nghiên cứu và đưa ra kết quả được biểu diễn bằng đồ thị sau : Hình 21: Sự tương quan thời gian trung bình của tín hiệu EEG Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 41 - Sử dụng hiểu biết này vào việc nén bằng cách điều chỉnh phương pháp nén thơng thường được biểu diễn ở hình 19 và bổ sung một số lối vào trễ cho bộ dự đốn. 3.2.1. Nén dự đốn với những lối vào trễ Ở hình 21 biểu diễn sự tương quan thời gian trung bình được tính tốn trên một tập huấn luyện tín hiệu EEG. Nhận thấy rõ ràng sự tương quan thời gian khơng chỉ tồn tại đối với những mẫu gần nhau, mà cịn ở những mẫu cĩ độ trễ khoảng 12 mẫu. Mức cực đại thu được cho độ trễ 12 mẫu tương ứng khoảng 10.6 Hz. Điều này được giải thích về mặt sinh học như sau: thực tế, sĩng alpha, dạng sĩng đặc trưng cho tín hiệu EEG bình thường, thuộc dải từ 8 – 13 Hz. Để lợi dụng ưu điểm của đỉnh tương quan sĩng alpha này chúng ta điều chỉnh (3.11) để tính tốn đến khoảng trễ dài hơn. Đặt N = {k|  k } xác định lân cận của độ trễ đã cho ở (3.11) được viết lại như sau: en = xn – f(xn-1, ..., xn-N, xn-, ...,xn-) (3.24) Giá trị tương quan từ hình 21 gợi ý rằng chọn N = 5,  = 10 và  = 15 sẽ cung cấp cho bộ dự đốn những mẫu quá khứ tương quan nhất. Thực tế, kết quả thực nghiệm cho thấy N và  -  cĩ thể chọn thấp hơn mà khơng giảm hiệu suất của bộ dự đốn, trong khi điều này sẽ làm cho nĩ đơn giản hơn và nhanh hơn. Kết quả chọn N = 2,  = 12, và  = 13. 3.2.2. Lượng tử hố vectơ của tín hiệu EEG Trong lượng tử hố vectơ chúng ta nhĩm lối ra nguồn thành những khối hay những vectơ. Ví dụ chúng ta coi L mẫu liên tiếp của tín hiệu là những thành phần của một vectơ N chiều. Vectơ của lối ra nguồn này tạo thành lối vào của bộ lượng tử hố vectơ. Tại cả bộ mã hố và giải mã của bộ lượng tử vectơ, sẽ cĩ một tậ hợp những vectơ N-chiều được gọi là sách mã (codebook) của bộ lượng tử. Những vectơ trong sách mã này, được hiểu là những vectơ mã (code-vectơ), sẽ được lựa chọn làm biểu diễn của vectơ tín hiệu chúng ta tạo ra từ lối ra nguồn. Mỗi vectơ mã sẽ được gán một chỉ số nhị phân. Tại mỗi bộ mã hố, vecơt lối vào được so sánh với mỗi vectơ mã để tìm ra vectơ mã gần nhất với vectơ lối vào. Những thành phần của vectơ mã này là những giá trị lượng tử của lối ra nguồn. Để cho bộ giải mã biết về vectơ mã nào đĩ được tìm thấy là gần với vectơ lối vào nhất, chúng ta truyền hay lưu trữ chỉ số nhị phân của vectơ-mã. Do bộ giải mã cĩ sách mã giống hệt bộ mã, nên cĩ thể khơi phục lại được vectơ mã được cho bởi chỉ số nhị phân của nĩ. Biểu diễn quá trình này bằng sơ đồ trực quan sau: Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 42 - Encoder Decoder ........ … Hình 22: Thủ tục lượng tử hố vectơ Diễn đạt theo một cách khác thì một bộ lượng tử hố vectơ k chiều và kích thước N là một phép ánh xạ Q từ một vectơ k chiều, trong khơng gian Ơclit Rk, vào một tập hữu hạn C bao gồm N lối ra hay những điểm mơ phỏng, được gọi là những mã vectơ hay những từ mã Q: Rk  C ở đĩ C = {y(1), y(2), .. y(N)} và y(i)  Rk đối với mỗi i {1, 2, …, N}. Tập C được gọi là sách mã hay đơn giản là mã. Áp dụng phương pháp này cho tín hiệu EEG bằng cách tính tốn những vectơ của những kênh lối vào và bằng cách xây dựng một sách mã cho tập vectơ này. Cĩ một sự biến đổi nhỏ là tính tốn đạo hàm thay cho những giá trị của kênh do đạo hàm EEG cĩ thể rất gần khơng. Vì vậy, với cùng một sách mã như nhau, cĩ thể thu được méo trung bình thấp hơn. Group into vectors Un- block Find closest code- vector codebook index Table lookup Source output reconstruction index x codebook Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 43 - CHƯƠNG 4: MƠ PHỎNG 4.1. Mã Huffman Sau đây mơ phỏng thuật tốn Huffman truyền thống với chiều dài từ mã khơng cố định tức là mỗi kí tự nguồn của nguồn sẽ cĩ từ mã của riêng nĩ. Thủ tục xây dựng mã dựa vào xác suất của các kí tự nguồn hồn tồn giống như đã trình bày ở trên. Hình 23 : tín hiệu nguồn và tín hiệu khơi phục sau khi nén và giải nén bằng phương pháp mã Huffman Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 44 - Hình 24 : tín hiệu lỗi giữa tín hiệu nguồn và tín hiệu giải nén. Kết quả: Name Size Bytes Class T 1x18432 147456 double array ans 32x1 147456 double array compr_data 1x38568 38568 uint8 array data 1x147456 147456 uint8 array decom_data 1x147456 147456 uint8 array info 1x1 1872 struct array recov_data 1x18432 147456 double array Grand total is 388886 elements using 777720 bytes tỉ lệ nén = 0.2616 hệ số nén = 3.8233 phần trăm tiết kiệm = 73.84% Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 45 - Nhận thấy nén tín hiệu EEG sử dụng mã Huffman khá hiệu quả: hệ số nén tương đối  4, phần trăm tiết kiệm khá cao 73.84%, mức độ phức tạp tính tốn thấp, và quan trọng nhất là nĩ cho phép khơi phục lại hồn tồn chính xác tín hiệu ban đầu. Nên đối với yêu cầu đảm bảo thơng tin chính xác mang trên tín hiệu EEG ghi được từ bệnh nhân để khơng gây ra sai sĩt trong việc chẩn đốn và kết luận lâm sàng đối với bệnh nhân, bác sĩ hồn tồn cĩ thể tin tưởng vào phương pháp nén này. Đối với những thiết bị lưu trữ và tính tốn ngày nay, phương pháp này tỏ ra rất hiệu quả. 4.2. Biến đổi DCT Mơ tả khái quát phương pháp sử dụng DCT transform: B1:Coi tín hiệu EEG vào là : data B2: Bước tiếp theo biến đổi DCT tín hiệu vào : DCT_data B3: Giữ lại N phần tử đầu tiên để gửi đi, cịn loại bỏ đi K phần tử cịn lại B4: biến đổi DCT ngược dữ liệu [N K]; ở đây K gồm K số 0 :gọi là recov_data B5: tính lỗi giữa tín hiệu thật và DCT ngược : err=data-recov_data B6: Lượng tử hố lỗi này, sau đĩ sử dụng Huffman coding để nén và truyền sai số này đi Ở bên nhận sẽ thực hiện như B4 sau đĩ lấy kết quả cộng với lỗi nhận được để khơi phục lại dữ liệu ban đầu. Kết quả mơ phỏng: Hình 25 : tín hiệu nguồn và sau khi khơi phục Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 46 - Hình 26 : tín hiệu lỗi tỉ lệ nén = 0.3336 phần trăm tiết kiệm = 66.64% Nhận thấy sử dụng biến đổi DCT để nén EEG cũng đạt được kết quả tương đối. Mặc dù sai số giữa tín hiệu khơi phục và tín hiệu ban đầu cũng khá nhỏ, song vẫn cĩ thể xảy ra xác suất gây lỗi chẩn đốn. Hơn nữa hiệu quả nén khơng cao bằng Huffman. Tuy nhiên nĩ cho phép mức độ tính tốn đơn giản Một vấn đề khĩ giải quyết hơn một chút trong quá trình mơ phỏng này là việc lượng tử hố lỗi. Khi lấy hệ số N khá cao thì sai số giữa tín hiệu nguồn và tín hiệu khơi phục khơng lớn. Nên ta cĩ thể sử dụng một số ít bit hơn để biểu diễn lỗi. Trong Matlab dữ liệu nĩ xử lý nhỏ nhất là 8 bit, điều này khiến cho việc mơ phỏng trong trường hợp này khơng bộc lộ hết hiệu quả mà tiềm năng của nĩ cĩ thể thực hiện được. Từ đĩ rút ra nhận xét là : tuỳ thuộc vào thiết bị phần cứng về tốc độ xử lý và khả năng lưu trữ mà chúng ta lựa chọn phương pháp nào cho phù hợp. Người ta cho rằng, phương pháp nén khơng mất thơng tin khơng giành được nhiều sự quan Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 47 - tâm bởi nĩ cho hiệu quả nén khơng cao, mà người ta tập trung nghiên cứu các phương pháp nén mất thơng tin để đạt được hiệu quả nén cao hơn. Song tín hiệu EEG đặc biệt cần thiết yêu cầu khả năng khơi phục lại hồn tồn dữ liệu đựơc ghi ban đầu, nên nếu sử dụng phương pháp nén mất thơng tin chúng ta bằng cách nào đĩ phải biến nĩ về loại khơng mất dữ liệu (ví dụ như nén lỗi và gửi cả lỗi như phương pháp biến đổi DCT ở trên). Khi đĩ về hiệu quả nén chúng ta cần phải xem xét kĩ, tuỳ vào từng trường hợp mà lựa chọn phương pháp nào hơn. Cĩ lẽ điều đáng quan tâm là ở mức độ phức tạp tính tốn? Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 48 - TÀI LIỆU THAM KHẢO [1] Guiliano Antoniol and Paolo Tonella.” EEG data compression techniques”. IRST, trento, Italy, Tech. Rep. 9508-03, 1997. [2] G.Nave and A. Cohen, “ECG compression using long-term prediction” IEEE trans. Biomed. Eng., Vol. 40, no. 9, pp. 877-885, Sept. 1993. [3] Ida Mengyi Pu.” fundamental data compression”.Nxb Elsevier.,2006 [4] J. Markel and A. Grey. Linear Prediction of speech. New york: Springer-Verlag, 1976. [5] Khalid Sayood .”Introduction to data compression”, third edition., Nxb Elseveer., 2006 [6] Leif Sưrnmo and Pablo Laguna. “Bioelectrical signal processing in cardiac and neurological applications”. tr.3-161 [7] Peyton Z. Peebles, Jr., Ph.D.” Probability, Random variables, and random signal principles” [8] PGS.TS. Nguyễn Bình.” Lý thuyết thơng tin”. tr. 3-63 [9] Trần Mạnh Tuấn.” Xác suất & thống kê lý thuyết và thực hành tính tốn”. Nxb ĐHQGHN . IV/2004 [10] Website : www.datacompression.com Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 49 - MỤC LỤC NỘI DUNG LỜI MỞ ĐẦU ............................................................................................................ 1 CHƯƠNG 1: GIỚI THIỆU CHUNG ....................................................................... 2 1.1. Nén dữ liệu ........................................................................................................ 2 1.2. Tín hiệu EEG (Electroencephalograph) và Sự cần thiết nén dữ liệu y sinh (Biomedical data compression) ................................................................................ 4 1.2.1. Tín hiệu EEG ............................................................................................. 5 1.2.2. Sự cần thiết nghiên cứu nén tín hiệu y sinh ................................................. 7 CHƯƠNG 2: LÝ THUYẾT NÉN DỮ LIỆU ............................................................ 9 2.1. Những vấn đề chung ......................................................................................... 9 2.2. Lý thuyết thơng tin .......................................................................................... 11 2.2.1. Khái niệm thơng tin .................................................................................. 11 2.2.2.2.Giới thiệu về lý thuyết thơng tin .......................................................... 12 2.3. Các phương pháp nén dữ liệu .......................................................................... 15 2.3.1. Các phương pháp nén khơng mất thơng tin ............................................... 15 2.3.1.1 Mã Huffman ....................................................................................... 15 2.3.1.2. Mã số học ........................................................................................... 19 2.3.1.3.Kĩ thuật từ điển .................................................................................... 22 2.3.1.4. Phương pháp nén dựa vào ngữ cảnh (context-based compression) ..... 23 1.4. Đo chất lượng nén ........................................................................................... 25 CHƯƠNG 3: NÉN TÍN HIỆU EEG ...................................................................... 26 3.1. Các phương pháp đã được sử dụng để nén EEG .............................................. 26 3.1.1. Các phương pháp nén khơng mất thơng tin (lossless compression) ....... 26 3.1.1.1. Giới thiệu phương pháp nén ............................................................... 26 3.1.1.2. Phương pháp mã Huffman ............................................................ 31 3.1.1.3. Nén đếm lặp ....................................................................................... 33 Nguyễn Thị Hương k49db Khĩa luận tốt nghiệp 7/5/2011 - 50 - 3.1.1.4. Kĩ thuật nén dự đốn (preditive compression techniques) ................... 35 3.1.1.4.2 Bộ dự đốn lọc số ......................................................................... 37 3.1.1.4.3. Dự đốn tuyến tính thích nghi .......................................................... 38 3.1.1.4. Phương pháp nén biến đổi (Transformation compression) ................. 39 3.1.2. Giới thiệu các phương pháp nén EEG khác ............................................... 40 3.2. Những đặc trưng của tín hiệu EEG .................................................................. 40 3.2.1. Nén dự đốn với những lối vào trễ ............................................................ 41 3.2.2. Lượng tử hố vectơ của tín hiệu EEG ....................................................... 41 CHƯƠNG 4: MƠ PHỎNG ...................................................................................... 43 4.1. Mã Huffman .................................................................................................... 43 4.2. Biến đổi DCT .................................................................................................. 45 TÀI LIỆU THAM KHẢO ....................................................................................... 48