Lưu trữ

Posts Tagged ‘Luby Transform’

Digital Fountain Code

Tháng Một 20, 2014 1 Bình luận

Muốn di chuyển một vật thể lớn, ta có thể tháo rời các bộ phận, di chuyển đến vị trí muốn dời đến, sau đó lắp ráp lại. Trong kỹ thuật truyền thông số truyền thống cũng vậy, cơ chế để truyền một tập tin là như sau: Trước hết tập tin được chia thành các gói tin (packet) nhỏ, sau đó từng gói tin được truyền đến địa chỉ nhận. Việc truyền tin hoàn thành nếu tất cả các gói tin được truyền đến địa chỉ nhận, và kết quả phải được phản hồi lại nơi truyền để gửi lại gói tin, nếu bị thất lạc.

Hãy xét trường hợp một máy chủ phân phối dữ liệu đến nhiều nguồn nhận. Sử dụng phương pháp truyền thống thì máy chủ cần duy trì kênh truyền hai chiều với các máy trạm, và phải duy trì danh sách thông tin máy trạm nào đã nhận các gói tin nào,… Việc này rất phức tạp và tốn kém, đặc biệt trên các kênh truyền nhiều nhiễu và dễ thất lạc gói tin. Chẳng hạn như việc điều khiển tàu thăm dò trên Sao Hỏa, mỗi tín hiệu được truyền (bằng tốc độ ánh sáng) ít nhất phải hơn 10 phút sau mới có thể đến được nơi nhận, do đó việc chờ đợi phản hồi để có thể gửi lại gói tin bị mất là không hiệu quả.

Ý tưởng giải pháp

image001

Trong mã vòi phun Digital Fountain (DF), giống như việc hứng các giọt nước từ một vòi phun, các gói tin có vai trò bình đẳng như nhau, và bộ thu nhận thu được càng nhiều “giọt” càng tốt. Sau đó, với một số lượng đủ lớn các gói (giọt) tin nhận được, có thể ráp lại thành dữ liệu cần truyền. Đặc điểm đó cũng là nguồn gốc cho tên gọi Vòi phun số: cốc nước sẽ đầy nếu nhận được nhiều giọt nước và không có sự phân biệt giữa các giọt.

Việc mã hóa là như sau:

  • Dữ liệu được chia nhỏ thành k phần,
  • Một số (trong k phần) được chọn, các phần đó được tổ hợp lại với nhau bằng phép XOR để hình thành một “giọt” tin. Mỗi giọt tin được liên kết với danh sách gồm các phần đã chọn (danh sách này thực tế được sinh ra một cách giả ngẫu nhiên).

Việc sinh giọt tin như vậy được lặp lại cho đến khi cần thiết. Có tất cả 2k lựa chọn khác nhau, tương ứng với các giọt khác nhau. Cuối quá trình mã hóa, sẽ có n giọt được sinh ra (thông thường n > k), mỗi giọt đều chứa trong mình thông tin gốc đã được pha trộn

Minh họa bằng hình ảnh:

Dữ liệu gốc, được chia thành k = 6 phần.

image002

Một “giọt” được sinh ra bằng phép XOR giữa các phần 1, 2 và 3. Giọt khác, được sinh ra từ các phần 1, 5 và 6:

image003

Giải mã:

Việc giải mã cũng giống như giải một hệ phương trình với k ẩn số (phần dữ liệu), trong đó mỗi “giọt” tin đóng vai trò một phương trình trong hệ. Như vậy, nói chung cần ít nhất k phương trình để giải.

image006

Trên thực tế, nếu chỉ với k giọt, trong hầu hết trường hợp thì xác suất để giải mã thành công chỉ là 30%. Để tăng xác suất giải mã, cần tăng số lượng giọt tin nhận được. Số lượng các giọt thừa quá được gọi là overhead: overhead lớn thì xác suất giải mã càng cao. Chẳng hạn, để xác suất lỗi nhỏ hơn 10-6, cần thừa quá 20 giọt. Chú ý rằng overhead là độc lập với k: với 20 giọt thừa quá sẽ cho xác suất lỗi nhỏ hơn 10-6 với mọi k. Vậy k lớn thì tốt hơn.

image007

Xác suất giải mã đối với mức thừa quá overhead.

Một số ứng dụng của DF Code:

  • Đa truyền (multicast) tin cậy: Có nhiều vấn đề khi truyền dữ liệu cho một số lượng lớn đích đến, như hàng loạt phản hồi về các gói gửi lỗi, không đồng nhất về thời gian bắt đầu truyền nhận, … DF Code giải quyết được các vấn đề trên: Mỗi người nhận sẽ nhận những gói họ có thể nhận, và dừng lại khi họ có đủ thông tin cần thiết.
  • Download song song: Có thể tổng hợp dữ liệu từ nhiều nguồn phát DF rời nhau để được dữ liệu cần lấy, chẳng hạn trong các mạng ngang hàng BitTorrent.
  • Truyền dữ liệu khoảng cách lớn: Tăng tốc độ truyền do không cần quan tâm đến phản hồi về các gói thất lạc.
  • Máy chủ web: Khi có nhiều kết nối đến cùng một file trên máy chủ, cần phải có bộ nhớ và trạng thái cho từng kết nối. Do giới hạn tài nguyên máy chủ, dẫn tới giới hạn về số kết nối đồng thời. Để giải quyết việc này, có thể sử dụng một DF để sinh ra các gói cho tất cả các kết nối tới file cần chia sẻ.
  • Video streaming: Truyền hình (gần như) thời gian thực.
  • Các ứng dụng khác: Hệ thống lưu trữ (chẳng hạn DropBox), vệ tinh địa tĩnh, …

Lời kết

Bài này chỉ mang tính chất tổng hợp một số thông tin, mang tính chất giới thiệu ý tưởng (theo người soạn) thú vị của DF Code dành cho các bạn chưa biết. Bạn đọc có thể tìm hiểu về các ứng dụng cụ thể hơn cũng cài đặt của một số hệ mã DF cụ thể:  Raptor code, Luby transform codes.

Tham khảo:

http://www.codeproject.com/Articles/425456/Your-Digital-Fountain

https://sites.google.com/site/andrealvitali2/VirtualHDDdigitalfountain.pdf

http://inst.eecs.berkeley.edu/~ee121/sp08/handouts/fountain.ppt

http://www.eecs.harvard.edu/~michaelm/TALKS/INFORMS06.ppt

Advertisements