唐诗的联想: 网络编码及三大应用 (Bob Li)

Presentation on theme: "唐诗的联想: 网络编码及三大应用 (Bob Li)"— Presentation transcript:

1 唐诗的联想: 网络编码及三大应用 (Bob Li)
Introduce Alfred & Helen, who shall narrate poems in Cantonese.

2 天子呼来不上船 Quiz: 唐诗名句 “天子呼來不上船, 自稱臣是酒中仙” 作者是: “诗仙” 李白 “诗圣” 杜甫 李商隐 杜牧

3 杜甫〈飲中八仙歌〉 知章騎馬似乘船，       李白一斗詩百篇， 長安市上酒家眠。 天子呼來不上船， 自稱臣是酒中仙。
      李白一斗詩百篇， 長安市上酒家眠。 天子呼來不上船， 自稱臣是酒中仙。       Ans：B; however A deserves partial credit.

4 長安市上酒家眠。 天子呼來不上船， 自稱臣是酒中仙。
李白一斗詩百篇， 長安市上酒家眠。 天子呼來不上船， 自稱臣是酒中仙。 七绝, 仄起平收 Pls narrate.

5 李白（701年－762），字太白，号青莲居士，唐朝诗人，有“诗仙”之称，伟大的浪漫主义诗人。汉族，出生于剑南道之绵州（今四川绵阳江油市青莲乡），一说生于西域碎叶城（今吉尔吉斯斯坦托克马克），5岁随父迁至剑南道之绵州（巴西郡）昌隆县（712年更名为昌明县），祖籍陇西郡成纪县（今甘肃天水市秦安县）。 其父李客，育二子（伯禽、 天然）一女（平阳）。存 世诗文千余篇，代表作 有《蜀道难》、《将 进酒》等诗篇，有 《李太白集》传世。 762年病逝于安徽 当涂，享年61 岁。其墓在 安徽当涂，四川江油、湖 北安陆有纪念馆。 百度 百科名片: This portrait is not the ridiculous one provided by 百科名片. 四川江油和湖北安陆打起了李白故居的官司 a few years ago。Guess who won.

6 百度 百科名片: 杜甫 杜甫（712－770），字子美，自号少陵野老，世称“杜工部”、“杜老”、“杜少陵”等。汉族，巩县（今河南巩义）人。杜甫曾祖父起由襄阳（今属湖北）迁居巩县。盛唐时期伟大的现实主义诗人。他忧国忧民，人格高尚，他的约1400余首诗被保留了下来，诗艺精湛，在中国古典诗歌中的影响非常深远，备受推崇。 年间曾居成都，后世有杜甫草堂纪念之。杜甫被世人尊为“诗圣”，其诗被称为“诗史”。杜甫与李白合称“李杜”，为了跟另两位诗人李商隐与杜牧即“小李杜”区别开来，杜甫与李白又合称“大李杜”。 《唐诗三百首》中独占38首。 数 paper杜甫是状元, 诗仙李白只是探花, 榜眼是王维(诗佛). 虽有杜甫草堂留下, 没有杜甫故居的官司。

7 百度 百科名片: 杜甫 杜甫（712－770），字子美，自号少陵野老，世称“杜工部”、“杜老”、“杜少陵”等。汉族，巩县（今河南巩义）人。杜甫曾祖父起由襄阳（今属湖北）迁居巩县。盛唐时期伟大的现实主义诗人。他忧国忧民，人格高尚，他的约1400余首诗被保留了下来，诗艺精湛，在中国古典诗歌中的影响非常深远，备受推崇。 年间曾居成都，后世有杜甫草堂纪念之。杜甫被世人尊为“诗圣”，其诗被称为“诗史”。杜甫与李白合称“李杜”，为了跟另两位诗人李商隐与杜牧即“小李杜”区别开来，杜甫与李白又合称“大李杜”。 《唐诗三百首》中独占38首。 但是，李白的百科名片没有提及杜甫，杜甫的提及李白4次，还提及李商隐与杜牧

8 My favorite 22 matrix 李 杜 大 李白 杜甫 小 李商隐 杜牧 大李杜, 小李杜

9 My favorite 22 matrix 李 杜 大 A. 李白 B. 杜甫 小 C.李商隐 D. 杜牧 这个talk第一个主角是…

10 百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 813年－約858年 祖籍陇西, same as 李白. In fact, 唐宗室 distant 后裔, 《唐诗三百首》paper counting 排第 4

11 Contents Network coding 唐诗 联想 李商隐 西昆诗派 NC = Butterfly Network
西昆诗派与李商隐有密切的关系

12 Contents Network coding 唐诗 联想 李商隐 西昆诗派 NC = Butterfly Network
(A) Wireless communications (B) Redundant storage (C) P2P content delivery 西昆诗派 3 parts of the talk containing 三大应用范畴 (D) Security

13 Part (A): Wireless communications
唐诗 Network coding 联想 Part (A): Wireless communications (1) 李商隐 Butterfly Network Wireless Butterfly Network Physical-layer NC 西昆诗派

14 Part (B): Redundant storage
唐诗 Network coding 联想 李商隐 Butterfly Network Wireless Butterfly Network Physical-layer NC NC for redundant storage Coding redundancy 西昆诗派 (B) 杜牧

15 Part (C): P2P content delivery
唐诗 Network coding 联想 李商隐 Butterfly Network Wireless Butterfly Network Physical-layer NC NC for redundant storage Coding redundancy 简介NC 理论 NC for P2P content delivery 西昆诗派 杜牧 (C) 禅师的偈子

16 Part (A): Wireless communications
唐诗 Network coding 联想 回想人生中的顿悟 李商隐 Butterfly Network Wireless Butterfly Network Physical-layer NC Butterfly Network Wireless Butterfly Network Physical-layer NC NC for redundant storage Coding redundancy Introduction to NC theory NC for P2P content delivery 西昆诗派 (2) Speaking of 禅师, 回想人生中的顿悟 杜牧 (3) 禅师的偈子

17 李商隐代表作 《锦瑟》锦瑟无端五十弦，一弦一柱思华年。 庄生晓梦迷蝴蝶，望帝春心托杜鹃。 沧海月明珠有泪，蓝田日暖玉生烟。
by Wikipedia 《锦瑟》锦瑟无端五十弦，一弦一柱思华年。 庄生晓梦迷蝴蝶，望帝春心托杜鹃。 沧海月明珠有泪，蓝田日暖玉生烟。 此情可待成追忆，只是当时已惘然。 《无题》昨夜星辰昨夜风，画楼西畔桂堂东。 身无彩凤双飞翼，心有灵犀一点通。 隔座送钩春酒暖，分曹射覆蜡灯红。 嗟余听鼓应官去，走马兰台类转蓬。 《无题》相见时难别亦难，东风无力百花残。 春蚕到死丝方尽，蜡炬成灰泪始干。 晓镜但愁云鬓改，夜吟应觉月光寒。 蓬山此去无多路，青鸟殷勤为探看。 《夜雨寄北》君问归期未有期，巴山夜雨涨秋池。 何当共剪西窗烛，却话巴山夜雨时。 Indirectly 刺激了 我人生中的顿悟 2018/12/8

18 顿悟led me to HK.  Today 有缘 to meet you all.
Details are skipped because of 30-min constraint.

19 李商隐代表作 《锦瑟》锦瑟无端五十弦，一弦一柱思华年。 庄生晓梦迷蝴蝶，望帝春心托杜鹃。 沧海月明珠有泪，蓝田日暖玉生烟。
by Wikipedia 《锦瑟》锦瑟无端五十弦，一弦一柱思华年。 庄生晓梦迷蝴蝶，望帝春心托杜鹃。 沧海月明珠有泪，蓝田日暖玉生烟。 此情可待成追忆，只是当时已惘然。 《无题》昨夜星辰昨夜风，画楼西畔桂堂东。 身无彩凤双飞翼，心有灵犀一点通。 隔座送钩春酒暖，分曹射覆蜡灯红。 嗟余听鼓应官去，走马兰台类转蓬。 《无题》相见时难别亦难，东风无力百花残。 春蚕到死丝方尽，蜡炬成灰泪始干。 晓镜但愁云鬓改，夜吟应觉月光寒。 蓬山此去无多路，青鸟殷勤为探看。 《夜雨寄北》君问归期未有期，巴山夜雨涨秋池。 何当共剪西窗烛，却话巴山夜雨时。 indirectly 刺激了 我人生中的顿悟 2018/12/8

20 网络编码 The title should be somewhat poetic.

21 In 科学人, 7/2007 络 Taiwan 科学人 magazine wants a story on 网络编码. easy story = recollection, including interactions 之前, never heard of this magazine Excerpted from Scientific American, 7/2007 Chinese edition

22 Figure adapted from Scientific American, Chinese 7/2007 edition
网络编码 与 蝴蝶 x = 0 or 1 y = 0 or 1 Every channels transmits one bit. Store-and-forward ？ Either x or y Figure adapted from Scientific American, Chinese 7/2007 edition 22

23 Figure adapted from Scientific American, Chinese 7/2007 edition
Store-and-forward Traffic jam Figure adapted from Scientific American, Chinese 7/2007 edition 23

24 Figure adapted from Scientific American, Chinese 7/2007 edition
Network coding (NC) xy = 0 if x = y 1 if x  y Decode y Decode x Figure adapted from Scientific American, Chinese 7/2007 edition 24

25 In 科学人, 7/2007 Becomes 网络 when translated by MS Office.
But, it is not this article that makes me 顿悟

26 In 科学人, 7/2007 An editor 这8个字令我顿悟 !
Main part of his article title = 8 words 这8个字令我顿悟 !

27 1. Linear network coding (NC) 2. Convolutional NC 3
1. Linear network coding (NC) Convolutional NC 3. NC theory via commutative algebra Construction of NC over cyclic networks 5. Martingale of patterns Computing by symmetry 7. Unified algebraic theory of sorting, routing, multicasting, & concentration networks 8. Cut-through coding Algebraic transform of multistage interconnection networks 10. Scalable nonblocking switches and geometric intuition 数 学 与 工 程 的 对 话 All my 小把戏 in making a living are under this theme.

28 Butterfly network 一举两得
Wireless transmission is multicasting in nature, perfect for applying NC. Multicasting Figure adapted from Scientific American, Chinese 7/2007 edition 28

29 Wireless version of Butterfly Network
x y x+y T R Wireless transmission is multicasting in nature, perfect for applying NC. 这就是 wireless butterfly network x y Physically,

30 Message exchange over Wireless Butterfly Network
Store-and-forward, 4 steps x y 2018/12/8

31 Message exchange over Wireless Butterfly Network
Store-and-forward, 4 steps to exchange a message through the middle relay x y 2018/12/8

32 Message exchange over Wireless Butterfly Network
Store-and-forward, 4 steps to exchange a message through the middle relay x y NC, 3 steps x y 2018/12/8

33 Message exchange over Wireless Butterfly Network
Store-and-forward, 4 steps to exchange a message through the middle relay x y NC, 3 steps xy xy this has been prototyped by MIT on the wireless LAN standard known as Wi-Fi or 2018/12/8

34 Communications on Mars
A+B A B A B B A An example from a proposal for NASA project. Satellite communications is so far analog. 2018/12/8

35 Optical application of wireless Butterfly Network
Did not happen 2000 years ago The 1st Emperor, who built the Great Wall The great defender against Hun over the Great Wall

36  昔秦皇汉武略输文采 这一句不是唐诗

37 如何可以略胜文采 ? Store-and-forward, 4 steps x y x y NC, 3 steps xy x y
(1 reception & 1 transmission, naturally) 2018/12/8

38 如何可以略胜文采 ? x y Store-and-forward, 4 steps x y NC, 3 steps xy 2 steps
+ can be algebraic or physical 2018/12/8

39 Physical-layer NC (PNC)
Step 1: Receive from multi-sources Superimposed electromagnetic waves with fading and noise 2018/12/8

40 Interference outcome  free higher throughput
Digital PNC [ZLL06] Interference outcome  free higher throughput Step 1: Receive from multi-sources 0/1  Cos(t) 2 Cos(t) or 0 Cos(t)  0/1 plus noise and fading Digital signal (Assuming perfect sync) 2018/12/8

41 Step 1a: Translation into binary
Digital PNC [ZLL06] Step 1a: Translation into binary 0/1  Cos(t) 2 Cos(t) or 0 (+ noise, fading) Cos(t)  0/1 (Not easy) Decode into: (= XOR) 2018/12/8

42 Digital PNC [ZLL06] Step 2: Broadcast XOR 2018/12/8

43 Analog PNC Step 1: Receive from multi-sources
Superimposed electromagnetic waves plus noise and fading MIT imitates & exposes CUHK work. The middle relay treat the signals as analog. Suit satellites over the earth. 2018/12/8

44 Step 2: Amplify and broadcast
Analog PNC Step 2: Amplify and broadcast 2018/12/8

45 Step 2: Amplify and broadcast
Analog PNC Step 2: Amplify and broadcast 2018/12/8

46 Step 2a : Decoding at each end (not easy)
Analog PNC Step 2a : Decoding at each end (not easy) 2018/12/8

47 Digital or analog PNC x y Store-and-forward, 4 steps x y NC, 3 steps x
PNC, 2 steps Decoding not easy 2018/12/8

48 百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 Decoding not easy Dense with 典故.

49 百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 宗法李商隐 = A gold mine Decoding not easy 西昆体, 诗派 like String Thy; cannot be proven wrong

50 They 酬唱 together and published happily.
百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 宗法李商隐 = A gold mine Decoding not easy 西昆体, 诗派 《西昆酬唱集》, 3 editors > 80%, make friends, trade awards, 无灾无难到公卿 They 酬唱 together and published happily.

51 They 酬唱 together and published happily.
百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 宗法李商隐 = A gold mine Decoding not easy 西昆体, 诗派 东汉郑玄以《毛诗传》为主，兼采今文三家诗说，加以疏解。谦敬不敢言注，故曰《<毛诗传>笺》=郑笺。 They 酬唱 together and published happily.

52 They 酬唱 together and published happily.
百度 百科名片: 李商隐 李商隐，著名诗人。擅长诗歌写作，骈文文学价值也很高，他是晚唐最出色的诗人之一，和杜牧合称“小李杜”，与温庭筠合称为“温李”，因诗文与同时期的段成式、温庭筠风格相近，且三人都在家族里排行第十六，故并称为“三十六体”。其诗构思新奇，风格秾丽，尤其是一些爱情诗和无题诗写得缠绵悱恻，优美动人，广为人传诵。但部分诗歌过于隐晦迷离，难于索解，至有“诗家总爱西昆好，独恨无人作郑笺”之说。因处于牛李党争的夹缝之中，一生很不得志。死后葬于家乡沁阳（今沁阳与博爱县交界之处）。作品收录为《李义山诗集》。 宗法李商隐 = A gold mine Decoding not easy 西昆体, 诗派 However, even 学李商隐的style 恐怕都需要科班出身 They 酬唱 together and published happily. 缺乏社會內容, 未学到李商隐诗歌精髓

53 Digital or analog PNC 宗法 PNC = A gold mine 现代版 西昆体
x y Store-and-forward, 4 steps x y NC, 3 steps 宗法 PNC = A gold mine x y PNC, 2 steps Decoding not easy The field of PNC mainly belongs Chinese researchers . 西昆诗派的后代? 现代版 西昆体 They all publish happily, with > 2 Chinese authors per paper. 2018/12/8

54 Part (B): Redundancy in Data Storage
Disk A B Backup A B This corresponds to store-and-forward. 略输文采 2018/12/8

55 Part (B): Redundancy in Data Storage
Single backup = NC RAIDs A B AB 2018/12/8

56 Perform NC over an imaginary network
Data Disks A B AB A’ 2018/12/8

57 Perform NC over an imaginary network
Data Disks A B AB A’ B’

58 Perform NC over an imaginary network
Data Disks A B AB A’ B’ AB

59 Redundancy in backup storage
Single backup RAIDs A B C D E F G H AB…H

60 To backup n disks by NC RAIDs A B C D E F G H AB…H D’ Single backup
2018/12/8

61 To backup n disks by NC RAIDs A B C D E F G H AB…H E’ D’
Single backup RAIDs A B C D E F G H AB…H E’ D’ 2018/12/8

62 Logical equivalent A parallel bus to transmit, say, a byte
Single backup RAIDs A B C D E F G H AB…H A parallel bus to transmit, say, a byte Bits A B C D E F G H A  B  … H = Parity check bit = Block coding = NC, too

63 Network coding or block coding
Coding is an art in optimizing redundancy. The greatest artist on redundancy is 杜牧.

64 百度 百科名片: 杜牧 杜牧（公元803－约852年），字牧之，号樊川居士，汉族，京兆万年（今陕西西安）人，唐代诗人。杜牧人称“小杜”，以别于杜甫。与李商隐并称“小李杜”。因晚年居长安南樊川别墅，故后世称“杜樊川”，著有《樊川文集》。 学其神来之笔 很难 七绝诗仙 in my opinion Underrated poet, even though he is in the GREAT 2x2 matrix.

65 杜牧代表作 by Wikipedia 清明 清明时节雨纷纷，路上行人欲断魂。借问酒家何处有，牧童遥指杏花村。 山行
远上寒山石径斜，白云深处有人家。停车坐爱枫林晚，霜叶红于二月花。 江南春 千里莺啼绿映红，水村山郭酒旗风。南朝四百八十寺，多少楼台烟雨中。 赤壁 折戟沉沙铁未销，自将磨洗认前朝。东风不与周郎便，铜雀春深锁二乔。 泊秦淮 烟笼寒水月笼沙，夜泊秦淮近酒家。商女不知亡国恨，隔江犹唱后庭花。 过华清宫 长安回望绣成堆，山顶千门次第开。一骑红尘妃子笑，无人知是荔枝来。 秋夕 银烛秋光冷画屏，轻罗小扇扑流萤。天阶夜色凉如水，卧看牵牛织女星。 遣怀 落魄江湖载酒行，楚腰纤细掌中轻。十年一觉扬州梦，赢得青楼薄幸名。 寄扬州韩绰判官 青山隐隐水迢迢，秋尽江南草未凋。二十四桥明月夜，玉人何处教吹箫。 头两句set up background，全诗重点在于后两句， 抒情得令人难忘。 原因之一是: 典故用得太 smooth.

66 杜牧代表作 by Wikipedia 清明 清明时节雨纷纷，路上行人欲断魂。借问酒家何处有，牧童遥指杏花村。 山行
远上寒山石径斜，白云深处有人家。停车坐爱枫林晚，霜叶红于二月花。 江南春 千里莺啼绿映红，水村山郭酒旗风。南朝四百八十寺，多少楼台烟雨中。 赤壁 折戟沉沙铁未销，自将磨洗认前朝。东风不与周郎便，铜雀春深锁二乔。 泊秦淮 烟笼寒水月笼沙，夜泊秦淮近酒家。商女不知亡国恨，隔江犹唱后庭花。 过华清宫 长安回望绣成堆，山顶千门次第开。一骑红尘妃子笑，无人知是荔枝来。 秋夕 银烛秋光冷画屏，轻罗小扇扑流萤。天阶夜色凉如水，卧看牵牛织女星。 遣怀 落魄江湖载酒行，楚腰纤细掌中轻。十年一觉扬州梦，赢得青楼薄幸名。 寄扬州韩绰判官 青山隐隐水迢迢，秋尽江南草未凋。二十四桥明月夜，玉人何处教吹箫。 二来，可能受佛家影响, 他喜用数字，也用得非常 smooth.

67 杜牧代表作 by Wikipedia 清明 清明时节雨纷纷，路上行人欲断魂。借问酒家何处有，牧童遥指杏花村。 山行
远上寒山石径斜，白云深处有人家。停车坐爱枫林晚，霜叶红于二月花。 江南春 千里莺啼绿映红，水村山郭酒旗风。南朝四百八十寺，多少楼台烟雨中。 赤壁 折戟沉沙铁未销，自将磨洗认前朝。东风不与周郎便，铜雀春深锁二乔。 泊秦淮 烟笼寒水月笼沙，夜泊秦淮近酒家。商女不知亡国恨，隔江犹唱后庭花。 过华清宫 长安回望绣成堆，山顶千门次第开。一骑红尘妃子笑，无人知是荔枝来。 秋夕 银烛秋光冷画屏，轻罗小扇扑流萤。天阶夜色凉如水，卧看牵牛织女星。 遣怀 落魄江湖载酒行，楚腰纤细掌中轻。十年一觉扬州梦，赢得青楼薄幸名。 寄扬州韩绰判官 青山隐隐水迢迢，秋尽江南草未凋。二十四桥明月夜，玉人何处教吹箫。

68 清明时节雨纷纷， 路上行人欲断魂。 借问酒家何处有， 牧童遥指杏花村。
To show: the greatest artist on redundancy is 杜牧. 3 consecutive versions

69 6言 清明节 雨纷纷， 路上人 欲断魂。 问酒家 何处有， 牧童指 杏花村。

70 5言 清明雨纷纷， 路人欲断魂。 酒家何处有， 童指杏花村。

71 4言 清明雨纷， 路人断魂。 酒家何处？ 指杏花村。 2018/12/8

72 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 Store-and-forward, 4 steps x y NC, 3 steps
PNC, 2 steps NC, 3 steps Decoding not easy 2018/12/8

73 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 Store-and-forward, 4 steps x y NC, 3 steps x
PNC, 2 steps Decoding not easy x y 2018/12/8

74 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 清明雨，人断魂。 酒何处？杏花村。 3言
Store-and-forward, 4 steps x y 清明雨，人断魂。 酒何处？杏花村。 NC, 3 steps x y PNC, 2 steps Decoding not easy x y 2018/12/8

75 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 清明雨，人断魂。 酒何处？杏花村。 3言 清明，断魂。 酒处？杏村。 2言
Store-and-forward, 4 steps x y 清明雨，人断魂。 酒何处？杏花村。 NC, 3 steps x y 也是 Decoding not easy 杜牧在这首诗里下了多少的 redundancy! 其结果：浑然天成, 千年以下 脍炙人口 清明，断魂。 酒处？杏村。 2言 Decoding not easy PNC, 2 steps Decoding not easy x y 2018/12/8

76 伟哉! 杜牧 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 清明雨，人断魂。 酒何处？杏花村。 3言 清明，断魂。 酒处？杏村。 2言
伟哉! 杜牧 清明雨纷，路人断魂。 酒家何处？指杏花村。 4言 3言 Store-and-forward, 4 steps x y 清明雨，人断魂。 酒何处？杏花村。 NC, 3 steps x y 清明，断魂。 酒处？杏村。 2言 Decoding not easy PNC, 2 steps Decoding not easy x y 2018/12/8

77 杜牧 代表作 清明 清明时节雨纷纷，路上行人欲断魂。借问酒家何处有，牧童遥指杏花村。 山行
远上寒山石径斜，白云深处有人家。停车坐爱枫林晚，霜叶红于二月花。 江南春 千里莺啼绿映红，水村山郭酒旗风。南朝四百八十寺，多少楼台烟雨中。 赤壁 折戟沉沙铁未销，自将磨洗认前朝。东风不与周郎便，铜雀春深锁二乔。 泊秦淮 烟笼寒水月笼沙，夜泊秦淮近酒家。商女不知亡国恨，隔江犹唱后庭花。 过华清宫 长安回望绣成堆，山顶千门次第开。一骑红尘妃子笑，无人知是荔枝来。 秋夕 银烛秋光冷画屏，轻罗小扇扑流萤。天阶夜色凉如水，卧看牵牛织女星。 遣怀 落魄江湖载酒行，楚腰纤细掌中轻。十年一觉扬州梦，赢得青楼薄幸名。 寄扬州韩绰判官 青山隐隐水迢迢，秋尽江南草未凋。二十四桥明月夜，玉人何处教吹箫。

78 One purpose: to 激励 民族意识

79 《桂枝香》王安石  (过片)   念往昔、繁华竞逐。叹门外楼头，悲恨相续。千古凭高对此，漫嗟荣辱。六朝旧事随流水，但寒烟芳草凝绿。至今商女，时时犹唱， 后庭遗曲。 || 老 狐 精 金陵怀古 调寄桂枝香。改革开放先驱 政敌苏东坡 被他整得很惨, 用字难免略带敌意

80 《桂枝香》王安石  (过片)   念往昔、繁华竞逐，叹门外楼头，悲恨相续。千古凭高对此，漫嗟荣辱。六朝旧事随流水，但寒烟芳草凝绿。至今商女，时时犹唱， 后庭遗曲。 || 老 狐 精 不是只有我一个人老是在用别人的话 旷古奇才王安石 也只是在重组别人的话 not easy being Chinese,文化悠久，人口众多. 好句子 …

81 Part (C): Introduction to NC theory & P2P application
s ‎When channel d ends at the node where channel e begins, the “adjacent pair” (d, e) corresponds by a red arrow inside the joining node. Channel d (d, e) Channel e Part (C) of this talk. Highways connected by a ramp.

82 Definition of a linear network code
s An F-linear network code assigns a coding coefficient kd,e  F, where the finite field F is the alphabet of data symbol. kd,e

83 Example of a linear network code
s An F-linear network code assigns a coding coefficient  F, where the finite field F is the alphabet of data symbol. Here, F = GRF(2) = {0, 1}.

84 Transmitted symbol s The source sends out symbols x and y through two channels. Every intermediate node makes a linear combination of incoming symbols for each of its outgoing channels. Through top-down telescoping, the symbol transmitted over every channel is a linear combination of x and y. x y x y x y x+y x+y x+y

85 Transmitted symbols = linear combinations of x & y
1 x = (x y)  y = (x y)  x+y = (x y)  x y x y x+y x+y x+y

86 · = (x y) Transmitted symbol Natural basis of F
1 1 1 1 The symbol transmitted over a channel e is written as (x y)  fe where fe is a column vector over F, called the coding vector. 1 1 1 The rest are calculated top-down. 1 1

87 Optimal network codes Fundamental Theorem of Linear NC [LY1998, LYC2003]. When |F| is large enough, there exists an optimal network code, that is: For every node v, incoming coding vectors to v span the dimension equal to maxflow from source to v. 2018/12/8

88 What if |F| is not large enough?
Q. Can two symbols be transmitted from s to all six receivers? // Here max flow from s to every receiver is 2. No, when a symbol means a bit. Yes, when a symbol means a byte. 并非因为Constructions in coding theory 常需要 large enough field，我们也照做 This example justifies such constraint. Actually any field but GF(2) would do. 2018/12/8

89 P2P content delivery by store-and-forward
Constant problems in Bit Torrent (BT) operation: Which packet to send to neighboring peers? Which packet to ask for from upstream? Heuristic algorithm of BT: Randomness at the beginning “Local rarest” scheme after a node has acquired a few packets. We can now talk about application of NC to P2P content delivery. 2018/12/8

90 P2P content delivery by store-and-forward
Constant problems in Bit Torrent (BT) operation: Which packet to send to neighboring peers? Which packet to ask for from them? 神秀禅师： 身是菩提树，心如明镜台，时时勤拂拭，勿使惹尘埃。 Heuristic algorithm of BT: Randomness at the beginning “Local rarest” scheme after a node has acquired a few packets. Heuristic algorithm also produces 尘埃 2018/12/8 90 90

91 P2P content delivery by store-and-forward Voided by random linear NC
Constant problems in Bit Torrent (BT) operation: Which packet to send to neighboring peers? Which packet to ask for from them? Voided by random linear NC Heuristic algorithm of BT: Randomness at the beginning “Local rarest” scheme after a node has acquired a few packets. 2018/12/8 91 91

92 P2P content delivery by random linear NC
Use random coding coefficients  a field of size 216 or 224. Allow the linear NC the flexibility of being secret, random, dynamically changing, … Every node includes the coding vector in the header of the transmitted packet. 1 2 3 4 … u v u+5v 2u+6v 3u+7v 4u+8v 5 6 7 8 Eventually any set of received packets with linearly independent coding vectors suffice for decoding. 2018/12/8

93 P2P content delivery by random linear NC Voided by random linear NC
Constant problems in Bit Torrent (BT) operation: Which packet to send to neighboring peers? Which packet to ask for from them? 六祖惠能： 菩提本无树，明镜亦非台，本来无一物，何处惹尘埃。 Voided by random linear NC Heuristic algorithm of BT: Randomness at the beginning “Local rarest” scheme after a node has acquired a few packets. Just use a little bit of Lin. Alg. Knowledge. 盛唐之世百花齐放，like HK today; but not so pragmatic Hubei dialect at that time was not so different from Cantonese. 一个文盲作出千古传诵的偈子 2018/12/8 93 93

94 百度 百科名片: 惠能 惠能（638年-713），俗姓卢氏，唐代岭南新州（今广东新兴县）人。佛教禅宗祖师，得黄梅五祖弘忍传授衣钵，继承东山法门，为禅宗第六祖，世称禅宗六祖。唐中宗追谥大鉴禅师。著有六祖《坛经》流传于世。是中国历史上有重大影响的佛教高僧之一。惠能禅师的真身，供奉在广东韶关南华寺的灵照塔中。

95 百度 百科名片: 惠能 惠能（638年-713），俗姓卢氏，唐代岭南新州（今广东新兴县）人。佛教禅宗祖师，得黄梅五祖弘忍传授衣钵，继承东山法门，为禅宗第六祖，世称禅宗六祖。唐中宗追谥大鉴禅师。著有六祖《坛经》流传于世。是中国历史上有重大影响的佛教高僧之一。惠能禅师的真身，供奉在广东韶关南华寺的灵照塔中。 至今 1300 年，真身不坏。 但抗战时被日本侵略者割开 Cut is covered by 袈裟

96 百度 百科名片: 神秀 神秀大师（公元606年-706年），唐代高僧的法号，是中国禅宗北派的开创者。唐汴州尉氏人（今河南省），俗姓李，为禅宗五祖弘忍弟子。弘忍死后，在荆州当阳山玉泉寺传法，声名远播。后为武则天召到京师，朝野景仰。因在北方传法，故其法系称为北宗。因南宗认为他所传的禅法是渐悟法门，故称其禅法为北渐或渐门。弟子有普寂、义福等。普寂的弟子道璇还把北宗禅传到日本。 神秀的北宗没几代就散了 Why 就散了？

97 NC 禅说 当场就顿悟！ 试问: “禅师, what is NC?” 神秀答: “Read this & that papers …
If necessary, more papers … 慢慢读、慢慢想 … xy = 0 if x = y 1 if x  y 渐渐就会懂.” 惠能答: “Look at Butterfly network.” 当场就顿悟！ Reason: 如果可以顿悟, 谁还需要渐悟. 我试作一个比方：… Prof. Wang of NCTU told me … 不管 speaker 难过 97

98 谢谢 11. Scalability of conditionally nonblocking switches
谢谢你们来, 也谢谢那些将好句子都先用掉的人 11. Scalability of conditionally nonblocking switches 12. Coding by algebraic topology