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

www.tudientoanhoc.net – Từ điển Toán học Anh Việt

Tháng Mười 1, 2013 Để lại bình luận

Hiện nay trên internet đã có một vài trang web cho phép tra từ điển toán học online. Theo tôi được biết, các trang này đều sử dụng nguồn dữ liệu từ cuốn sách sau (dưới dạng file PDF):

Từ điển Toán học Anh – Việt với khoảng 17000 từ. Nhà xuất bản KH và KT In lần thứ 2 – 1976 Tập thể hiệu đính: Phan Đức Chính, Lê Minh Khanh, Nguyễn Tấn Lập, Lê Đình Thịnh, Nguyễn Công Thuý, Nguyễn Bác Văn Tiểu ban duyệt: Lê Văn Thiêm, Phan Đình Diệu, Trần Vinh Hiển, Nguyễn Cảnh Toàn, Nguyễn Đình Trí, Hoàng Tuỵ

Việc tra cứu tài liệu trên máy hoặc tra cứu bằng cách in tài liệu ra đều bất tiện. Do vậy việc cần thiết là xây dựng ứng dụng từ điển để tiện tra cứu trên máy hoặc môi trường web.

Thực tế, do việc chuyển đổi dữ liệu từ file tài liệu trên, nên các trang tra cứu từ điển hiện thời có những nhược điểm sau:

  • Từ thiếu nhiều (so với file tài liệu), chẳng hạn trang http://tudientoan.seotopten.net/ dẫn đầu trong kết quả tìm kiếm (do được SEO tốt), nhưng tôi được biết trang này hiện chỉ mới có khoảng 3200 từ (quá thiếu so với file PDF gốc)
  • Từ sai (do file gốc có nhiều sai sót chế bản),
  • Tra cứu không thuận tiện (chậm, khó tìm theo ý muốn)

Do vậy tôi đã tự mình thực hiện chuyển đổi lại dữ liệu từ file trên một cách (gần như tuyệt đối) đầy đủ, và viết một trang web tra cứu online, đó chính là http://www.tudientoanhoc.net

Cũng phải nói thêm rằng mặc dù file PDF trên có giới thiệu từ điển khoảng 17000 từ, nhưng thực ra khi chuyển đổi thành dữ liệu bảng tôi biết được chỉ có khoảng gần 15000 mục tra cứu, trong đó số đầu từ gốc ít hơn nhiều: khoảng 5300 từ, còn lại là các từ dẫn xuất. Tôi không được biết cuốn từ điển (bản in) gốc có số lượng từ như thế nào?

Việc chuyển đổi, chuẩn hóa dữ liệu là mất thời gian nhất, dựa vào một số quy tắc sắp thứ tự từ điển mà tôi đã phải xử lý chính tả bằng tay khá nhiều từ (khoảng 400 từ). Các từ này, trong một số bộ dữ liệu từ điển miễn phí (chẳng hạn của Hồ Ngọc Đức), cũng sai chính tả. Việc lập trình tôi chỉ viết đơn giản, viết từ đầu, trong thời gian ngắn, nên giao diện còn chưa bắt mắt và (có thể) chậm. Tôi sẽ hiệu chỉnh dần trong quá trình vận hành.

Mong trang web có ích phần nào cho các bạn trong quá trình tham khảo các tài liệu toán tiếng Anh. Mọi đóng góp, bình luận, yêu cầu tính năng, … các bạn có thể gửi tại blog này hoặc tới email handuc@gmail.com

Hàn Đức.

TECSUN PL-600 USER MANUAL

Tháng Tám 20, 2013 Để lại bình luận

Đây là link tải file tôi lược dịch (chỉ các phần chính) hướng dẫn sử dụng Radio hiệu TECSUN PL-600, tôi mua tặng Bố tôi hồi Tết nguyên đán. Chia sẻ cho bạn nào tình cờ tìm kiếm hướng dẫn Tiếng Việt của Radio này mà chưa thấy: http://www.mediafire.com/view/ox4aox11a6i8ghb/HDSD_Tecsun.docx

Còn đây là bản gốc tiếng Anh: http://www.mediafire.com/view/91n6iopli28inhi/Tecsun_PL-600.pdf

Chuyên mục:Uncategorized

Google reader alternative

Tháng Sáu 8, 2013 Để lại bình luận

image

Hôm nay mới chuyển qua dùng Feedly thay cho Google Reader sắp bị khai tử vào tháng 7 tới. Thấy có vẻ ổn vì không như cái chức năng takeout của google chỉ ra metadata còn dữ liệu bài thì không trích được. Các dữ liệu cũ kể cả khi link gốc bài viết đã không còn (như blog entry yahoo ngày xưa) vẫn được lưu đầy đủ trên GR thì giờ đây có thể chuyển qua Feedly. Quá trình chuyển đổi rất nhanh và đăng nhập dùng luôn google account. Thậm chí có vẻ còn có nhiều tính năng hay hơn GReader.
Feedly cũng tích hợp nhiều ứng dụng đọc RSS khác như Reeder, Press,… và có ứng dụng trên các nền tảng iOS, Android. Bạn nào đang dùng Google reader có thể tham khảo chuyển qua dùng Feedly nhé!

DXNTool – SourceCode Generator, and more..

Tháng Năm 19, 2013 Để lại bình luận

Insertion Script

Khi lập trình các ứng dụng cơ sở dữ liệu, nhiều lúc chúng ta cần những tiện ích đơn giản dùng để sinh (generate) ra các mã trình một cách tự động từ cấu trúc cho trước. Đối với một bảng dữ liệu trong một hệ quản trị CSDL nào đó, có thể bạn đã và sẽ cần một tiện ích có các tính năng sau:

(1)    Generate câu lệnh tạo bảng;

(2)    Generate chuỗi insert dữ liệu của bảng đó;

(3)    Generate tài liệu về bảng (database table documentation) để lưu trữ;

(4)    Kết xuất (export) dữ liệu bảng ra file excel;

(5)    Generate Business Object class tương ứng theo cấu trúc bảng để thuận tiện cho việc viết mã trong các ứng dụng;

Các tính năng này, hoặc đã có sẵn trong các công cụ quản trị CSDL (chẳng hạn, SQL Server Management Studio), hoặc có thể có rải rác trong các tiện ích miễn phí và trả tiền (chẳng hạn, Tier Dev), hoặc có những hướng dẫn viết code để tự làm ra chúng trên các website về lập trình. Có thể kể ra một vài đường link sau:

http://www.codeproject.com/Articles/19719/Generate-Insertion-Scripts-Using-NET-2-0

http://www.codeproject.com/KB/codegen/TierGenerator.aspx

http://smartcodegenerator.codeplex.com/

Sau nhiều lần thử cài đặt các công cụ và tải các mã nguồn kèm hướng dẫn về chạy thử, tôi thấy chưa thật sự thỏa mãn. Do công cụ quá cồng kềnh cho một tính năng nhỏ, do công cụ quá cứng ngắc đầu ra (thay đổi phải sửa hardcode), do công cụ tốt thì phải trả tiền mà cũng không đủ các tính năng mình mong muốn,… tôi đã tự viết công cụ với các tính năng cho riêng mình.

Công cụ với mục tiêu là các tính năng nêu trên tôi đang viết vào những lúc rảnh và cũng không thật rốt ráo (cần đến đâu viết đến đó), và vẫn bổ sung dần dần các tính năng khác như generate toàn bộ một project mẫu với chức năng CRUD đầy đủ, đầu ra tùy biến theo template chỉnh sửa được. Chắc chắn rằng nhiều người đã tự làm cho mình các công cụ như vậy (chẳng hạn đồng nghiệp và bạn bè mà tôi biết) vì mỗi người mong muốn các tính năng khác nhau cho riêng mình.

Tôi xin được chia sẻ công cụ này (vẫn còn vài bug exception) cho bạn nào chưa tìm được công cụ nhỏ gọn, portable của riêng mình có thể tham khảo sử dụng, với các tính năng (1)-(4) và các ưu điểm:

–          Làm việc trên 3 Hệ quản trị CSDL thường gặp là MS SQL Server, Oracle, MySQL (có thể bổ sung các loại khác),

–          Có thể tùy biến template (file XSLT) để thay đổi output như mong muốn (hiện áp dụng cho tính năng (3)). Về nguyên tắc, có thể generate ra mã nguồn của một ngôn ngữ tùy ý,

–          Rất nhỏ gọn,

–          Portable (không cần cài đặt).

Bạn nào quan tâm, cần bổ sung các tiện ích khác có thể trao đổi thêm để hoàn thiện.

Download Here

Generate table documentation

Hình: Generate table documentation (có thể save as thành file .htm)

Ebook 80 bài toán thông minh

Tháng Năm 2, 2013 Để lại bình luận

Cảm ơn Diễn đàn Toán học đã chia sẻ tại đây

Chuyên mục:Ebook, Toán học

Viết bài bằng ăn roi xem

Tháng Mười Một 5, 2012 Để lại bình luận

image

Chị Minh Thư có quả kính rất ngầu này.
(Android test)

Chuyên mục:Family