Thư viện bài tháng 01 năm 2010

GT 6: Thử nhóm bất ứng biến giải mã nhanh

Ngô Quang Hưng | 29 tháng 01, 2010 | Bản để in Bản để in

6. Thử nhóm bất ứng biến giải mã nhanh

6.1. Ý tưởng của Kautz-Singleton

Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận {d}-phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số {1} trên cột) đủ lớn và nếu hai cột bất kỳ có phần giao đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nối mã (code concatenation) để xây dựng một ma trận thỏa tính chất thứ nhất. Chúng ta thảo luận ý tưởng của Kautz-Singleton trước, sau đó chỉ ra cách dùng ý tưởng này và một ý mới để xây dựng ma trận phân cách giải mã nhanh được.

Bổ đề 1 Gọi {{\bf M}} là một ma trận nhị phân {t \times N} mà mỗi cột có cân nặng ít nhất là {w}, và phần giao của hai cột bất kỳ (các số {1} chung của hai cột) có lực lượng nhiều nhất là {\lambda}. Thì, {{\bf M}} là ma trận {d}-phân-cách với bất kỳ {d} nào thỏa mãn {d\lambda+1 \leq w}. Cụ thể là {{\bf M}} sẽ là ma trận {\left\lfloor \frac{w-1}{\lambda} \right\rfloor}-phân-cách.

Bổ đề này dễ chứng minh. Ta nói tiếp ý tưởng thứ hai. Trước hết hãy định nghĩa phép nối mã.

Gọi {C_{\text{out}}} là một mã {(n_1,k_1)_q}, nghĩa là một ánh xạ từ {\mathbb F_q^{k_1}} vào {\mathbb F_q^{n_1}}, trong đó {q = 2^{k_2}}. (Phép nối mã có thể định nghĩa tổng quát hơn, nhưng ta không cần điều đó.) Như vậy, mỗi ký tự mã của {C_{\text{out}}} là một thành viên của tập {\mathbb F_q} gồm {2^{k_2}} phần tử, và vì thế cũng có thể xem như một thành viên của tập {\mathbb F_2^{k_2} = \{0,1\}^{k_2}}. Mỗi một từ mã của {C_{\text{out}}}{n_1} vị trí. Mã {C_{\text{out}}} sẽ được gọi là mã ngoài (outer code).

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận (2) »

GT 5: Sơ lược lý thuyết mã hóa

Ngô Quang Hưng | 26 tháng 01, 2010 | Bản để in Bản để in

5. Sơ lược lý thuyết mã hóa

Claude Shannon là cha đẻ của lý thuyết thông tin và lý thuyết mã hóa. Sẽ không có truyền thông hiện đại nếu không có Shannon. Nhà toán học lỗi lạc Kolmogorov từng nói về Shannon như sau: “Trong thời buổi mà kiến thức nhân loại càng lúc càng đuợc chuyên môn hóa, Claude Shannon là một nhà khoa học ngoại lệ. Shannon kết hợp các ý tưởng toán học sâu sắc với các hiểu biết rộng và cụ thể của các vấn đề quan trọng bậc nhất của công nghệ. Shannon là một trong những nhà toán học vĩ đại nhất đồng thời là một trong những kỹ sư giỏi nhất trong vài thập niên qua”. Nếu câu nói đó được phát biểu lúc này, thì phải thay “vài thập niên qua” bằng “thế kỷ 20″. Bài này duyệt qua một số kiến thức cơ bản về lý thuyết mã hóa cần cho thử nhóm.

5.1. Ý tưởng của Shannon (và Hamming)

Ý tưởng chính của lý thuyết mã hóa là thêm thông tin vào từng thông điệp trước khi gửi đi để bên nhận có thể tự phát hiện lỗi hoặc thậm chí tự sửa lỗi xảy ra trên đường truyền. Hai tham số chính của một mã là tỉ lệ (rate) của thông tin nguyên thủy trên thông tin gửi đi, và khả năng chịu đựng lỗi — số lỗi tối đa mà mã có thể dùng để kiểm tra hoặc sửa lỗi.

Cụ thể hơn, giả sử ta làm việc trên an-pha-bê {\Sigma}. Trong truyền thông số thì thông thường {\Sigma = \{0,1\}^m} với số tự nhiên {m} nào đó vì thường chỉ có 2 bits {0}{1}. Trong lý thuyết mã hóa thì {\Sigma} có thể tổng quát hơn, là một trường {\mathbb F_q} chẳng hạn. Chuyển từ an-pha-bê {\mathbb F_q} sang an-pha-bê nhị phân không khó khăn gì. Nhưng ta cứ xét một an-pha-bê tổng quát trước đã. Giả sử mỗi thông điệp gửi đi có chiều dài {k}, nghĩa là mỗi thông điệp gửi đi là một vector trong {\Sigma^k}. Thay vì gửi một thông điệp {{\bf x} \in \Sigma^k}, ta gửi {{\bf y} = E({\bf x})} là ảnh của {{\bf x}} dưới ánh xạ mã hóa {E: \Sigma^k \rightarrow \Sigma^n}. Chúng ta cần {{\bf y}} chứa nhiều thông tin hơn {{\bf x}}, để cho bên nhận — dù có nhận một bản bị lỗi của {{\bf y}} — thì vẫn có thể hồi phục lại {{\bf x}}. Do đó {n > k}.

Đọc tiếp toàn bài »

Chuyên mục: Combinatorics & Lý thuyết mã hóa & Thuật Toán | Bình luận »

Ý tưởng tồi tệ nhất trong lịch sử

Ngô Quang Hưng | 22 tháng 01, 2010 | Bản để in Bản để in

Trong lịch sử không có gì tệ hơn ý tưởng rằng mình có thể đi chỗ này ngồi nhìn lên cây


chuẩn bị cho 2 buổi nói chuyện tuần sau đó. Tại vì bận làm mấy cái này:



Thế cho nên thân gửi các anh chị tôi hân hạnh được gặp tuần sau, xin thông cảm nếu tôi không “make sense”.

(Đừng thắc mắc, tôi hít đất có 1 cái thôi!)

Chuyên mục: Vui - Giải Trí | Bình luận (6) »

Một nốt buồn

Ngô Quang Hưng | 13 tháng 01, 2010 | Bản để in Bản để in

Giáo sư Sam Roweis, khoa KHMT của NYU, vừa nhảy từ tầng 16 tự tử hôm qua. Cách đây vài năm ông có buổi nói chuyện ở khoa tôi. Rất thông minh và energetic. Nghe nói gần đây ông có cặp con gái song sinh, sinh sớm, bị “severe disability”.

Chuyên mục: Tin tức đó đây | Bình luận (8) »

Các câu hỏi phỏng vấn [33]

Ngô Quang Hưng | 13 tháng 01, 2010 | Bản để in Bản để in

Cảm ơn bác Vũ Hà Văn cho câu hỏi số 90 rất dễ thương. Câu 91 là một sinh viên của tôi vừa phỏng vấn ở Google được/bị hỏi. Câu 92 chôm từ chùa THT, do bác Đàm Thanh Sơn truyền bá từ quyển sách thú vị của Mark Levi.

  1. Có 10 con kiến trên một que 1 mét. Từng con kiến bắt đầu bò sang trái hoặc phải tùy hỉ, dọc theo que, với tốc độ 1 mét/giờ. Khi hai con kiến đụng đầu nhau chúng sẽ đổi hướng. Khi một con bò đến đầu que thì nó rới xuống đất. Hỏi: khi nào thì tất cả kiến rơi xuống đất?
  2. Cho n dãy ký tự, mỗi dãy có n ký tự. Tìm dãy con chung lớn nhất của tất cả n dãy trong thời gian càng nhanh càng tốt. Ví dụ, ba dãy abcxyz, xabcfb, xyzabc có dãy con abc chung.
  3. Một người đi xe đạp hai bánh trong sân. Vết bánh trước và bánh sau tạo thành hai đường cong trơn khép kín không giao nhau. Chứng minh rằng diện tích hình vành khăn nằm giữa hai đường cong khép kín này là một hăng số chỉ phụ thuộc vào cái xe đạp, không phụ thuộc gì vào cơ bắp hay nghệ thuật của người đi.

Chuyên mục: Dành cho du học sinh & Vui - Giải Trí | Bình luận (13) »

Academic Careers

Ngô Quang Hưng | 06 tháng 01, 2010 | Bản để in Bản để in

Hôm qua (05 tháng 1, 2010) tôi có một bài nói chuyện ở hội nghị VEF 2010. Hy vọng nó cũng hữu dụng cho một số bạn đọc blog, xin post lại bài ở đây. Do nói bằng tiếng Anh, tôi đã chuẩn bị bài bằng tiếng Anh, và bây giờ không có thời gian dịch nó ra tiếng Việt. Hội nghị đã được tổ chức rất tốt. Tôi gặp được rất nhiều người thú vị và học được nhiều điều. Cảm ơn các bạn trong ban tổ chức đã cho cơ hội.


Hello everyone. Thanks very much for attending my talk. I’m honored to be invited and humbled to be sandwiched between these two hugely successful gentlemen. I actually had no idea what this talk is supposed to be about until roughly a week ago when Tường sent me an email with the following excerpt

Dear anh Hung,
Blah blah blah ...
In the current agenda, the title of your part in the plenary session is "academic careers".
This is really a broad topic under the "All the way home" session name.

That is why you will hear something vaguely in the realm of “academic careers,” about which I have no authority whatsoever.

Why in the world did I agree to go give a talk when I didn’t even know the title, and even after knowing the title I am less than qualified to give it? Here’s why:

  • Amount I was paid: $400
  • The round-trip Amtrak ticket from Buffalo to Troy: $128
  • A chance to network with the future of Vietnam’s science and technology: priceless
    (As you can see, I watched too much TV.)

Đọc tiếp toàn bài »

Chuyên mục: Dành cho du học sinh & Giáo dục | Bình luận (19) »

Chúc mừng năm mới muộn

Ngô Quang Hưng | 01 tháng 01, 2010 | Bản để in Bản để in

Thời gian bay. Bài này đã 30 năm tuổi.

It’s the end of the decade
In another ten years time
Who can say what we’ll find
What lies waiting down the line

Chuyên mục: Âm Nhạc | Bình luận »