Tài liệu Sửa lỗi mạng dùng mã hóa không gian con

ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI ĐỖ TIẾN DŨNG SỬA LỖI MẠNG SỬ DỤNG MÃ HÓA KHÔNG GIAN CON LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG Hà Nội - 2012 ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI ĐỖ TIẾN DŨNG SỬA LỖI MẠNG SỬ DỤNG MÃ HÓA KHÔNG GIAN CON Ngành: Công Nghệ Điện Tử - Viễn Thông Chuyên ngành: Kỹ thuật điện tử Mã số: 60 52 70 LUẬN VĂN THẠC SĨ CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG Hà Nội - 2012 ii MỤC LỤC LỜI CAM ĐOAN ................................................................................................ i MỤC LỤC ........................................................................................................... ii DANH SÁCH THUẬT NGỮ VIẾT TẮT ........................................................ iv DANH SÁCH HÌNH VẼ .................................................................................... v LỜI CẢM ƠN .................................................................................................... vi TÓM TẮT ......................................................................................................... vii CHƢƠNG I: GIỚI THIỆU ................................................................................ 1 CHƢƠNG II: TỔNG QUAN KỸ THUẬT MÃ MẠNG ................................. 6 2.1 Giới thiệu. ................................................................................................... 6 2.2 Kỹ thuật mã mạng ....................................................................................... 6 2.2.1 Định lý cơ bản của kỹ thuật mã mạng .................................................. 6 2.2.2 Ưu điểm của kỹ thuật mã mạng ............................................................ 7 2.3 Kỹ thuật mã mạng tuyến tính .................................................................... 10 2.4 Kỹ thuật mã mạng tuyến tínhngẫu nhiên .................................................. 12 CHƢƠNG III: MÃ SỬA LỖI MẠNG ............................................................ 14 3.1 Operator channel. ...................................................................................... 14 3.2 Mã hóa cho kênh operator. ........................................................................ 16 3.2.1 Khoảng cách giữa hai không gian véc-tơ trong ......................... 16 3.2.2 Mã ....................................................................................................... 17 3.2.3 Điều kiện để khôi phục mã. ................................................................ 18 3.2.4 Mã có kích thước không đổi. .............................................................. 19 3.3 Các giới hạn về tốc độ mã hóa. ................................................................. 19 3.3.1 Giới hạn Hamming. ............................................................................ 20 3.3.2 Giới hạn quả cầu Hilbert..................................................................... 21 3.3.2 Giới hạn mã Singleton. ....................................................................... 22 3.4 Phương pháp xây dựng mã sửa lỗi mạng. ................................................. 24 3.4.1 Bộ tạo mã. ........................................................................................... 24 3.4.2 Bộ giải mã. .......................................................................................... 25 3.5 Tổng kết .................................................................................................... 27 iii CHƢƠNG IV: MÔ PHỎNG ........................................................................... 28 4.1 Giới thiệu phần mềm. ................................................................................ 28 4.1.1 Cài đặt và sử dụng phần mềm. ........................................................... 28 4.1.2 Cấu trúc phần mềm. ............................................................................ 28 4.1.3 Giao diện phần mềm. .......................................................................... 30 4.2 Mô phỏng. ................................................................................................. 31 4.2.1 Cấu trúc gói tin. .................................................................................. 34 4.2.2 Hoạt động của nút nguồn. ................................................................... 34 4.2.2 Hoạt động của nút trung gian. ............................................................ 35 4.2.3 Hoạt động của nút đích. ...................................................................... 36 CHƢƠNG V: KẾT LUẬN ............................................................................... 39 5.1 Kết luận. .................................................................................................... 39 5.2 Hướng nghiên cứu trong tương lai. ........................................................... 39 TÀI LIỆU THAM KHẢO ............................................................................... 40 PHỤ LỤC .......................................................................................................... 41 iv DANH SÁCH THUẬT NGỮ VIẾT TẮT Ký hiệu Tiếng Anh Tiếng Việt NC Network Coding Kỹ thuật mã mạng LNC Linear Network Coding Kỹ thuật mã mạng tuyến tính RLNC Random Linear Network Coding Kỹ thuật mã mạng tuyến tính ngẫu nhiên NECO Network Coding Simulator Phẩn mềm mô phỏng NECO UML Unifield Modelling Language Ngôn ngữ mô hình hóa thống nhất v DANH SÁCH HÌNH VẼ Hình 1.1: Mô hình mạng cánh bướm ................................................................... 1 Hình 2.1: Mạng cánh bướm .................................................................................. 8 Hình 2.2: Kỹ thuật mã mạng trong mô hình mạng không dây ............................. 9 Hình 2.3: Bảo mật thông tin trong kỹ thuật mã mạng ....................................... 10 Hình 3.1: Minh họa khôi phục mã ...................................................................... 18 Hình 3.2: Minh họa giới hạn mã Hamming ....................................................... 21 Hình 3.3: Minh họa mã Hilbert .......................................................................... 22 Hình 3.4: Minh họa mã Singleton ...................................................................... 23 Hình 3.5: Giới hạn tốc độ mã hóa cho một một mã trong đồ thị Grassmann ... 23 Hình 4.1: Sơ đồ UML cho module core ............................................................. 29 Hình 4.3: Giao diện phần mềm NECO............................................................... 30 Hình 4.4: Sơ đồ mạng ......................................................................................... 32 Hình 4.5: Tùy chọn đường truyền trong mô phỏng............................................ 32 Hình 4.6: Tùy chọn Protocol .............................................................................. 33 Hình 4.8: Xác suất mất mát đường truyền 0.2 ................................................... 38 Hình 4.9: Xác suất mất mát đường truyền 0.9 ................................................... 38 vii TÓM TẮT Kỹ thuật mã mạng là một kỹ thuật truyền tin mới được đưa ra cho mô hình phát đa điểm (multicast) bằng cách cho phép các nút mạng trung gian mã hóa thông tin nó nhận được trước khi gửi đi, được đề xuất bởi Ahlswede và đồng nghiệp năm 2000 [1]. Tuy nhiên, trong mạng không dây, do kênh truyền bị ảnh hưởng bởi pha đinh, thông tin được mã hóa tại các nút mạng có thể bị lỗi và lỗi này sẽ tiếp tục tích lũy từ nút mạng này đến nút mạng khác, gây nên lỗi tin của toàn mạng tại các nút đích. Giải pháp thường dùng là áp dụng phương pháp mã kênh tại từng nút mạng để làm giảm thiểu lỗi mạng. Thay vì vậy, một hướng mới đang được nhiều người quan tâm đến là mã hóa trên không gian chiếu (còn gọi là KK codes), được đề xuất bởi Koetter và Kschischang năm 2008, trên nền kỹ thuật mã mạng tuyến tính ngẫu nhiên. KK codes mở rộng kỹ thuật channel-error correction thành network-error correction, trong đó thay vì gửi một véc-tơ thì người ta gửi một không gian véc-tơ. Ở đầu nhận, sau khi nhận được một không gian véc-tơ khác, có bị tác động của nhiễu, ta cần tìm lại không gian véc-tơ đã được gửi. Có rất nhiều công cụ phục vụ cho việc mô phỏng mạng như NS-2, OPNET, GLOMOSIM, Matlab với các ngôn ngữ lập trình khác nhau: C++, JAVA, Python … Luận văn này sử dụng phần mềm mô phỏng NECO dựa trên ngôn ngữ lập trình Python để mô phỏng sửa lỗi mạng dùng mã KK. Đây là một công cụ mô phỏng mới và được sử dụng ngày càng phổ biến bời các nhà nghiên cứu kỹ thuật mã mạng. 1 CHƢƠNG I GIỚI THIỆU Xét một mô hình mạng truyền thông như hình vẽ: Hình 1.1: Mô hình mạng cánh bướm Giả sử rằng nút trên cùng muốn gửi 2 bit dữ liệu x và y đến cả hai nút phía dưới (multicasting) trong thời gian nhanh nhất. Dễ thấy rằng phương pháp truyền trong hình là tối ưu, với giả sử rằng tốc độ truyền trên các cạnh của đồ thị là như nhau. Ví dụ này dẫn đến ý tưởng sau: Nếu ta cho phép các nút trung gian (như các router trên Internet) tham gia thay đổi các gói dữ liệu, thì có khả năng sẽ tiết kiệm được thông lượng, độ trễ và các tài nguyên khác trong mạng.[6] Từ ý tưởng trên, kỹ thuật mã mạng (NC: Network Coding) được đề xuất trong lĩnh vực lý thuyết thông tin bởi Ahlswede (2000). Thay vì chỉ đơn thuần chuyển tiếp thông tin, các nút mạng trung gian có thể tổ hợp lại một vài gói tin đầu vào và biến thành một hoặc nhiều gói tin đầu ra. Như vậy, NC chính là một hình thức hợp tác ở tầng mạng. Với hình thức này, NC cho phép các nút trung 2 gian sinh ra các gói tin mới, và có thể được xem là một cách tổng quát hóa của phương thức định tuyến trong mạng truyền thống. Những ưu điểm của NC so với định tuyến truyền thống:  Sử dụng hiệu quả hơn tài nguyên mạng(tăng băng thông và công suất).  Hiệu quả tính toán.  Tăng tính bền vững (robustness) giúp chống lại những thay đôỉ về cấu hình của mạng.  Tăng tính bảo mật thông tin. Để hiểu rõ hơn, ta định nghĩa một bài toán cụ thể như sau: Mô hình mạng dưới dạng một đồ thị trực tiếp giả sử đỉnh là một đồ thị acyclic. Trong , để đơn giản ta có 1 đỉnh là nguồn (source) và một số gọi là đích (sink). Ta muốn truyền dữ liệu từ source đến tất cả các sink trong thời gian ngắn nhất, với giả sử dung năng mỗi cạnh bằng 1 (một đơn vị dữ liệu truyền trên một đơn vị thời gian). Khi đó, với việc sử dụng kỹ thuật mã mạng, các nút trung gian có thể kết hợp các gói tin đến nó để tạo ra một gói tin mới. Giả sử tất cả các gói tin đến đều có kích thước là k (tức là thuộc trường ). Việc kết hợp các gói tin có thể coi như một hàm số. Một bộ các hàm số như vậy được gọi là mã mạng (network code). Nếu tất cả các mã mạng cho phép giải mã ở đích thì ta gọi là một network coding solution. Nếu tất cả các hàm là tuyến tính, tức là gói tin lối ra là tổ hợp tuyến tính của các gói tin lối vào thì ta có một mã mạng tuyến tính. Quay lại bài toán mã mạng, định lý của Ahlswede có thể được hiểu như sau: bằng cách trộn dữ liệu tại các nút trung gian của mạng, thông tin được truyền từ nút nguồn tới nút đích với tốc độ tối đa bằng giá trị min-cut giữa chúng. 3 Định lý và chứng minh của Ahlswede cho biết luôn tồn tại một network coding solution nhưng không chỉ ra phương pháp kết hợp các gói tin để đạt được tốc độ truyền tin lớn nhất. Tuy nhiên, vào năm 2003 Li và các đồng nghiệp [3] đã chỉ ra phương pháp mã tuyến tính (linear coding) tại các nút trung gian để đạt được tốc độ truyền tin lớn nhất từ nguồn tới đích. Trong [3], khái niệm mã mạng tuyến tính và cách xây dựng mã trong truyền tin đa điểm của mạng tuần hoàn và không tuần hoàn được chỉ ra. Một phương pháp mã hóa được đề xuất [5] là các nút trung gian lựa chọn các hệ số mã hóa tuyến tính một cách ngẫu nhiên. Phương pháp này được gọi là mã mạng tuyến tính ngẫu nhiên (random linear NC). Không giống như phương pháp mã mạng tuyến tínhngẫu nhiên quyết định (deterministic linear NC), mã mạng tuyến tínhngẫu nhiên không thể đạt đến dung năng đa điểm với xác suất đơn vị nhưng vấn đề truyền thông đa điểm có thể thực hiện với xác suất hàm mũ khi chiều dài mã . Bài báo chỉ ra rằng, xác suất mã mạng ngẫu nhiên được tìm ra sẽ giảm khi số đường liên kết lớn, và ngược lại sẽ tăng khi kích thước trường hữu hạn càng lớn . Ngày nay, NC là hướng nghiên cứu được rất nhiều người quan tâm vì những ưu điểm cũng như tiềm năng của nó trong lĩnh vực mạng và truyền thông. Tuy nhiên, truyền thông trên thực tế đối mặt nhiều với vấn đề nhiễu, nhiễu có nhiễu đường truyền hoặc các gói tin độc được đưa vào với mục đích phá hoại. Lúc này bắt đầu xuất hiện khái niệm sửa lỗi mạng, mục đích chính của nó là thiết kế một mã mạng có thể sửa được lỗi gây ra trong quá trình truyền tin. Năm 2003, Kotter và Kschischang đã đề xuất một phương pháp thiết kế mã mạng sửa lỗi cho mã mạng ngãu nhiên tuyến tính. Ý tưởng này đã khởi nguồn cho một lĩnh vực nghiên cứu mới được biết đến với cái tên mã không gian con hay mã sửa lỗi trong không gian chiếu (error-correction code design in projective spaces).Một mô hình truyền tin ứng dụng kỹ thuật mã mạng được 4 đề xuất, thay vì là các véc-tơ, đầu vào và đầu ra của mô hình là các không gian con của một không gian nào đó. Những khái niệm mới từ đó cũng phải được định nghĩa để phục vụ cho mục đích mã hóa và giải mã như khoảng cách giữa hai không gian véc-tơ, các loại mã không gian con cùng với những giới hạn của các loại mã đó. Luận văn này sẽ mô phỏng lại một mã sửa lỗi cho mã mạng tuyến tínhngẫu nhiên trên thực tế dựa trên thuật toán mã hóa và giải mã được đề xuất bởi Kotter và Kschischang. Công cụ mô phỏng được sử dụng trong luận văn là NECO, một công cụ mô phỏng mới được giới thiệu năm 2009 và được sử dụng rộng rãi trong lĩnh vực nghiên cứu mã mạng (network coding) trong những năm gần đây. Phần mềm mô phỏng này được viết trên ngôn ngữ lập trình bậc cao Python.Đây là ngôn ngữ rõ ràng, dễ đọc nên giảm thời gian phát triển và nâng cao hiệu suất cũng như dễ bảo trì và mở rộng chương trình. Python cũng được sử dụng rộng rãi cho các ứng dụng khoa học, và đặc biệt có hai thư viện toán học và kỹ thuật tuyệt vời là SAGE và Pylab có sẵn và miễn phí. Tất cả các thư viện sử dụng để phát triển mô phỏng được cho phép bởi GPL (GNU General Public License) và là mã nguồn mở. Về cơ bản NECO được chia thành các mô-đun lõi và mô-đun mở rộng. Các mô-đun lõi cung cấp các tính năng thiết lập tối thiểu như các giao thức định tuyến cơ bản, tạo đồ thị, lập lịch, giao diện người dùng đồ họa và dòng lệnh. Mô-đun mở rộng để phát triển các chức năng cơ bản, tính toán các giao thức phức tạp hơn. Đặc điểm chính của phần mềm NECO bao gồm:  Xác định các mô hình mạng.  Các giao thức của kỹ thuật mã mạng.  Quan sát hoạt động của mạng cũng như các tham số thống kê khác.  Mô phỏng được viết toàn bộ bằng Python và dễ dàng mở rộng các module 5 Luận văn được tổ chức thành các phần: Chương 2: Tổng quankỹ thuật mã mạng. Chương 3: Mã sửa lỗi mạng. Chương 4: Mô phỏng. Chương 5: Kết luận và hướng nghiên cứu tiếp theo. 6 CHƢƠNG II TỔNG QUAN KỸ THUẬT MÃ MẠNG 2.1 Giới thiệu Trong các hệ thống mạng truyền thống, thông tin có thể được ghép kênh, đóng gói, định tuyến… nhưng vẫn tồn tại trong mạng như những thực thể độc lập, các nút mạng không làm thay đổi thông tin, bản tin đi ra một nút là bản sao của bản tin lối vào. Năm 2000, Ahlswede và các đồng nghiệp đã đề xuất một kỹ thuật mới đầy triển vọng trong mạng truyền thông, đó là kỹ thuật mã mạng (network coding). Với kỹ thuật này các nút mạng không chỉ chuyển tiếp mà còn xử lý thông tin mà nó có được bằng cách kết hợp chúng lại và truyền đi, để rồi sau đó nơi nhận vẫn tách ra được thông tin nó cần nhận. Kỹ thuật này đã chững minh được những ưu điểm của nó về tiết kiệm tài nguyên mạng cũng như tăng tính bảo mật thông tin. Ngày nay, kỹ thuật mã mạng đã trở thành một hướng nghiên cứu được rất nhiều nhà khoa học hướng đến bởi những ứng dụng rộng rãi của nó trong xử lý thông tin, xử lý ảnh và truyền thông. 2.2 Kỹ thuật mã mạng 2.2.1 Định lý cơ bản của kỹ thuật mã mạng Định lý 1 : Xét một đồ thị có hướng không tuần hoàn là tập hợp các đỉnh, , với là tập các cạnh của đồ thị. Giả sử rằng từng cạnh có dung năng đơn vị, có nguồn phát đơn vị nằm trên cùng một đỉnh của đồ thị và phát dữ liệu đến bộ thu. Giá trị lát cắt nhỏ nhất (min-cut) đến từng bộ thu là sẽ tồn tại một giản đồ truyền đa điểm trên một trường hữu hạn đủ lớn thì , trong 7 đó các nút mạng trung gian sẽ kết hợp tuyến tính những ký hiệu đi đến nó trên , phân phát thông tin từ đỉnh phát đồng thời tới tất cả các đỉnh thu ở tốc độ . Định lý này có thể được xem như là định lý Max-flow Min-cut cho lý thuyết thông tin mạng: Định nghĩa 1: Xét một mạng được biểu diễn bởi đồ thị và . Gọi lần lượt là tập các đỉnh và cạnh có dung năng đơn vị. là nút nguồn của mạng và muốn truyền thông tin đến nút đích  Một lát cắt giữa và là phép phân hoạch các nút của đồ thị thành các tập rời nhau.  Lát cắt nhỏ nhất là lát cắt có giá trị nhỏ nhất.  Giá trị của một lát cắt bằng tổng dung năng của các cạnh trong lát cắt. Định lý 2: Xét một mạng được biểu diễn bằng đồ thị như được định nghĩa ở trên. Nếu lát cắt nhỏ nhất giữa và bằng thì thông tin được truyền từ với tốc độ lớn nhất bằng . Tương đương, tồn tại chính xác đến đường dẫn phân biệt từ nút nguồn tới nút đích. Từ định lý trên, ta biết rằng tồn tại đường dẫn phân biệt từ nút nguồn tới nút đích. Do nhiều nút đích cùng sử dụng mạng đồng thời, tập hợp những đường dẫn này sẽ có thể chồng lên nhau. Dễ thấy là chúng phải chia sẻ tài nguyên với nhau và do vậy làm giảm tốc độ truyền. Tuy nhiên, định lý một đã nói rằng nếu ta cho phép nút trung gian không chỉ truyền mà còn kết hợp thông tin thì các nút đích sẽ thu được cùng một tốc độ giống như là chỉ có duy nhất nó sử dụng tài nguyên mạng. Kỹ thuật mã mạng giúp tađạt được điều này. 2.2.2 Ƣu điểm của kỹ thuật mã mạng Thông lƣợng Hình 2.1 mô tả một mạng truyền thông như là một đồ thị có hướng trong đó các đỉnh là các thiết bị đầu cuối và cạnh tương ứng với kênh truyền. Giả sử 2 nguồn cẩn truyền thông tin và tới 2 bộ thu , . 8 Hình 2.1: Mạng cánh bướm [10] Theo truyền thống, bit thông tin vậy cạnh nhận được sẽ truyền hoặc được xử lý độc lập với nhau vì . Nếu ta truyền nhận được cả , trong khi định truyền đi bit hoặc và và thì bộ thu . Ngược lại nếu sẽ chỉ quyết . Sử dụng ý tưởng của kỹ thuật mã mạng, ta có thể cho phép các nút trung gian xử lý thông tin nó có thay vì chỉ chuyển tiếp chúng. Cụ thể, nút có thể làm phép “xor” hai thông tin truyền đi qua cạnh khôi phục lại được nhận được { . và tạo ra và }, từ đó giải các phương trình . Tương tự như vậy đối với . Ví dụ này chỉ ra rằng nếu ta cho phép các nút trung gian trong mạng kết hợp chuỗi thông tin và tách thông tin tại nơi nhận thì chúng ta có thể tăng được thông lượng của hệ thống. Tiết kiệm tài nguyên mạng không dây Với thông tin vô tuyến, kỹ thuật mã mạng mang lại nhiều lợi ích đối với tuổi thọ pin, băng thông không dây và độ trễ. Xét một mạng không dây ad-hoc, trong đó hai thiết bị và như là thiết bị chuyển tiếp. muốn trao đổi hai tập tin nhị phân sử dụng 9 Hình 2.2: Kỹ thuật mã mạng trong mô hình mạng không dây [10] Với kỹ thuật mã mạng được áp dụng, ta có những ưu điểm về mặt dung lượng của kênh vô tuyến: nút nhận được cả hai tập tin và thực hiện phép “xor” chúng để tạo ra tập tin mới, tập tin này sau đó được quảng bá tới cả hai bộ thu. Nút được đã có và từ đó giải mã được . Nút có và giải mã . Phương pháp này có những ưu điểm về mặt sử dụng năng lượng (nút tiết kiệm được năng lượng vì chỉ cần truyền một lần thay vì hai như trước), thời gian trễ ( quá trình truyền hoàn tất chỉ trong 3 lần truyền thay vì 4), băng thông vô tuyến (sử dụng kênh vô tuyến trong thời gian ngắn hơn). Bảo mật Việc gửi đi kết hợp tuyến tính các gói tin thay vì truyền dữ liệu chưa mã hóa giúp nâng cao tính bảo mật một cách tự nhiên, tránh những trường hợp nghe trộm. Như vậy, với những hệ thống muốn tránh những xâm nhập đơn giản, ta sẽ không cần thêm cơ chế bảo mật nào nữa. Ví dụ trong hình 2.3, nút gửi thông tin tới nút thông qua hai đường và . Thông tin được kết hợp và gửi đi, nếu một đối tượng tại nút trung gian nào đó lấy cắp dữ liệu thì cũng không thể giải mã được, chỉ nơi thu khi nhận đủ thông tin cần thiết từ các nguồn khác nhau mới có thể khôi phục lại thông tin ban đầu. 10 Hình 2.3: Bảo mật thông tin trong kỹ thuật mã mạng [10] 2.3 Kỹ thuật mã mạng tuyến tính (LNC) Đình lý về kỹ thuật mã mạng được nêu ở phần trên chỉ ra rằng bằng việc kết hợp dữ liêu tại các nút trung gian của mạng, thông tin từ nguồn tới đích có thể được truyền qua mạng với tốc độ lớn nhất bằng giá trị lát cắt nhỏ nhất giữa chúng. Tuy nhiên, định lý không chỉ ra làm cách nào để đạt được tốc độ lớn nhất đó. Năm 2003, Li và đồng nghiệp [3] đã chứng minh được có một phương pháp có thể đạt được điều đó, đó chính là mã mạng tuyến tính. Một vấn đề quan trọng của mã mạng tuyến tính là cách xây dựng mã mạng (network code), hay nói cách khác là tim các hệ số của các hàm mã hóa tại các nút trung gian để nơi thu có thể khôi phục lại bản tin nguồn từ các gói tin nhận được. Tập các hệ số thỏa mãn điều kiện có thể khôi phục lại được gọi là network coding solution. Câu trả lời đơn giản và có hệ thống được Koetter và Medard đưa ra vào năm 2003 dựa trên các phép toán đại số[9]. Có sự liên hệ giữa network code solution với phương pháp giải các phương trình tuyến tính. Một vài kết quả quan trọng được các nhà nghiên cứu trong lĩnh vực này sử dụng một cách rộng rãi. Trước khi chỉ ra những kết quả đó, ta sẽ bắt đầu với một vài ký hiệu và định nghĩa. Một mạng được biểu diễn là một đồ thị có hướng tập các nút mạng (các đỉnh của đồ thị) và , với là là tập các đường truyền trong mạng (các cạnh của đồ thị). Giả sử rằng thông tin được truyền từ nút tới nút với mọi 11 Định nghĩa 2: Với một đường truyền nói chung , nút được gọi là điểm bắt đầu và điểm kết thúc. Với một đường truyền bắt đầu và kết thúc được ký hiệu là thông tin truyền trên đường truyền và , điểm Sử dụng kỹ thuật mã mạng, là hàm mã hóa các gói tin nhận được tại điểm bắt đầu Định nghĩa 3: Gọi thu. { lần lượt là số bản tin nguồn cần phát và số bộ }, { } là tập các nút nguồn và nút đích. Dữ liệu nguồn cũng như dữ liệu được truyền trên đường truyền là chuỗi các bít véc-tơ là các phần tử của trường hữu hạn của nút đích Dữ liệu đầu ra thứ với là tổ hợp tuyến tính của các dữ liệu đi trên đường truyền của nó: ∑ trong đó tính trong (2.1) là thông tin truyền trên đường truyền , có được bằng kết hợp tuyến các dữ liệu nguồn (nếu có) : ngẫu nhiên đã được tạo ra trước đó ∑ : ∑ Tập các hệ số { các dữ liệu hoặc (2.2) } được chọn từ trường là bài toán cho kỹ thuật mã mạng. Từ hai định nghĩa trên, ta có hai kết quả quan trọng sau: Định lý 3: Coi các hệ số { | |, { ma trận } được lấy trong ma trận } được lấy từ ma trận kích thước | | kích thước | |. Bộ | |, và { kích thước } được lấy từ được gọi là một mã mạng tuyến tính (linear network code). Việc ánh xạ các bản tin nguồn [ [ ] tới các dữ liệu nhận được ] tại một đích nào đó được biểu diễn: ( ) (2.3) 12 , là ma trận đơn vị. Với Định lý 4: Bộ mã mạng tuyến tính có thể giải được nếu ma trận truyền từng bộ thu với trên trường có bậc đầy đủ hạn đối với . Khi đó, bài toán kết nối đa điểm có thể được giải quyết. Một vấn đề quan trọng đằng sau việc xây dựng mã mạng tuyến tính cho kỹ thuật mã mạng là biết được kích thước phù hợp của trường hữu hạn để có thể giải quyết được bài toán truyền đa điểm. Kích thước trường càng lớn, độ phức tạp tính toán trong mạng càng lớn. Thực tế, các biểu thức đại số trong kỹ thuật mã mạng được thực hiện trên các từ mã có độ dài . Định lý 5 : Đối với bài toán truyền đa điểm với nguồn độc lập và có bộ thu. Trong cả trường hợp mạng không tuần hoàn có lỗi hoặc không có lỗi xảy ra, tồn tại mã mạng tuyến tính trong trường nếu . 2.4 Kỹ thuật mã mạng tuyến tínhngẫu nhiên (RLNC) Các định lý cơ bản nói trên dựa trên việc tính toán cho mã mạng tuyến tính quyết định (deterministic linear network code) trong truyền tin đa điểm. Nói cách khác các hệ số { } được chọn để thông tin nguồn được tái tạo lại từ các bộ thu với xác suất bằng một. Tức là mạng lúc này là mạng có cấu trúc tập trung, các hệ số được tạo ra và phân phát bởi một trung tâm nào đó. Một phương pháp được đề xuất đó là mã mạng tuyến tínhngẫu nhiên, các nút mạng sẽ lựa chọn các hệ số mã hóa một cách tuyến tính. Không giống như phương pháp mã mạng tuyến tính quyết định, phương pháp này không thể đạt được xác suất đơn vị, nhưng có thể đạt được xác suất hàm mũ với chiều dài mã Định lý 6 : Xét bài toán truyền đa điểm với các thông tin nguồn độc lập, bộ thu, các hệ số mã hóa { } được chọn ngẫu nhiên, đồng đều 13 trên trường bằng với ⁄ với . Xác suất để bộ mã mạng có thể được giải ít nhất sẽ là số đường truyền liên quan các hệ số mã hóa. Như vậy, định lý này đã chỉ ra rằng, số đường truyền liên quan đến các hệ số mã hóa càng lớn thì xác suất giải bộ mã mạng càng nhỏ, kích thước trường hữu hạn càng lớn thì xác suất giải bộ mã mạng càng lớn.