پایان نامه ﺗﺌﻮری رﻣﺰﮔﺬاری و راﺑﻄﻪ آن ﺑﺎ ﻋﻠﻢ ﻛﺎﻣﭙﻴﻮﺗﺮ

ﭼﻜﻴﺪه:

ﺑﺎ اﻳﺠﺎدﻛﺎﻣﭙﻴﻮﺗﺮو اﻓﺰاﻳﺶ ﺗﻌﺪادﻛﺎرﺑﺮان آن، ﻣﺴﺌﻠﻪرﻣﺰﮔﺬاریو رﻣﺰﻧﮕﺎریﻛﻪاز ﻗﺪﻳﻢ ﻧﻴﺰوﺟﻮدداﺷﺖ، ﺟﻨﺒﻪ ﺟﺪﻳﺪوﻣﻬﻤﻲ را ﺑﻪ ﺧﻮدﮔﺮﻓﺖ. رﻣﺰﻧﮕﺎریورﻣﺰﮔﺬاریﻫﻨﺮﻧﻮﺷﺘﻦ ﺑﻪ ﺻﻮرترﻣﺰاﺳﺖ، ﺑﻄﻮرﻳﻜﻪﻫﻴﭻ ﻛﺲ ﺑﻪﻏﻴﺮازدرﻳﺎﻓﺖﻛﻨﻨﺪه ﻣﻮردﻧﻈﺮ، ﻧﺘﻮاﻧﺪﻣﺤﺘﻮایﭘﻴﻐﺎمرا ﺑﺨﻮاﻧﺪ. اﻳﻦ ﻛﺎر ﺑﻪ ﺧﺎﻃﺮدﻻﻳﻞ ﻣﺨﺘﻠﻔﻲ اﻧﺠﺎمﻣﻲ ﺷﻮدﻛﻪاز ﻣﻬﻤﺘﺮﻳﻦ آن دﻻﻳﻞ ﻣﻲ ﺗﻮان ﺑﻪاﻣﻨﻴﺖاﻳﺠﺎد ﺷﺪه و ﺣﻔﻆ ﻣﺤﺘﻮای ﭘﻴﺎمﻫﺎ و اﻃﻼﻋﺎتدرﻫﻨﮕﺎماﺳﺘﻔﺎده از آن اﺷﺎرهﻛﺮد. در اﻳﻦ ﻣﻘﺎﻟﻪ ﻣﻄﺎﻟﺒﻲ رادر ارﺗﺒﺎط ﺑﺎ ﺗﺌﻮریﻛﺪﻳﻨﮓ واﻧﻮاع روش ﻫﺎیآن ﺑﻴﺎن ﻣﻲ ﻛﻨﻴﻢ.

ﻛﻠﻴﺪ واژه ﻫﺎ:

رﻣﺰﮔﺬاری، ﺗﺌﻮری رﻣﺰﮔﺬاری،ﻛﺪﮔﺬاری ﻣﻨﺒﻊ،ﻛﺪﮔﺬاریﻛﺎﻧﺎل، ﺗﺌﻮریرﻣﺰﮔﺬاری ﺟﺒﺮی،ﻛﺪ ﺳﺪﻛﻨﻨﺪه ﺧﻄﻲ،ﻛﺪ ﺣﻠﻘﻪای، روش آﻟﺒﺮﺗﻲ، رﻣﺰﮔﺬاریﻣﺘﻘﺎرن، رﻣﺰﮔﺬاریﻧﺎﻣﺘﻘﺎرن، RSA

ﻣﻘﺪﻣﻪ:

رﻣﺰﮔﺬاریﻳﺎﻫﻤﺎن رﻣﺰﻧﮕﺎری، ﻳﻚ ﻧﻮع ﻋﻠﻢ وﻫﻨﺮﻣﺤﺴﻮبﻣﻲ ﺷﻮد. ﻋﻠﻢ اﺳﺖ، ﭼﻮن درون آن اﻟﮕﻮرﻳﺘﻢ ﻫﺎیزﻳﺎدی وﺟﻮد داردﻛﻪدر ﺑﻌﻀﻲ ﻣﻮاﻗﻊ ﭘﻴﭽﻴﺪه اﻧﺪو در ﺛﺎﻧﻲ ﻫﻨﺮاﺳﺖ، ﭼﻮن اﺳﺘﻔﺎدهﻛﺮدن از اﻟﮕﻮرﻳﺘﻢ ﻫﺎ ﺑﻪﻧﺤﻮﻣﻨﺎﺳﺐودرﺟﺎیﺧﻮد، ﭼﻴﺰیﻛﻤﺘﺮازﻫﻨﺮﻧﻴﺴﺖ. رﻣﺰﻧﮕﺎریدردﻧﻴﺎیﺗﺠﺎریاﻣﺮوز ﺑﺴﻴﺎر اﻫﻤﻴﺖدارد، ﭼﻮن ﻛﻪ ﺳﺎده ﺗﺮﻳﻦ وﻛﺎرﺑﺮدی ﺗﺮﻳﻦ روش ﺣﻔﺎﻇﺖاز دادهﻫﺎﻳﻲ اﺳﺖﻛﻪﺑﻪ ﺻﻮرت اﻟﻜﺘﺮوﻧﻴﻜﻲ، ذﺧﻴﺮه، ﭘﺮدازش و اﻧﺘﻘﺎل داده ﻣﻲ ﺷﻮﻧﺪ)آﻧﮕﻮﻳﻦ ﺟﻮﻟﻴﺎ،20000(

ﻣﻮرداﺳﺘﻔﺎده رﻣﺰﮔﺬاریدر ﺑﺴﻴﺎریاز اﻣﻮرﻛﺴﺐوﻛﺎر ﻣﻲ ﺑﺎﺷﺪ. ﺑﺮایﻣﺜﺎل، اﻳﻦ اﺟﺎزه را ﺑﻪﺗﺠﺎر ﻣﻲ دﻫﺪﺗﺎ ﺷﻤﺎرهﺣﺴﺎبﻫﺎی ﻣﺸﺘﺮﻳﺎن ﺧﻮد را ﻣﺤﺎﻓﻈﺖﻧﻤﺎﻳﻨﺪو داد و ﺳﺘﺪﻫﺎی ﺧﻮد را ﺑﻪ ﺧﻮﺑﻲ وﺑﺎ اﻃﻤﻴﻨﺎن اﻧﺠﺎمدﻫﻨﺪ. ﺣﺘﻲ در ﻣﻮردﻗﺮاردادﻫﺎی ﻗﺎﻧﻮﻧﻲ ﻛﻪﺑﺎﻳﺪاز ﻃﺮﻳﻖ اﻳﻨﺘﺮﻧﺖاﻧﺘﻘﺎل داده ﺷﻮﻧﺪ، رﻣﺰﮔﺬاری، اﻣﻨﻴﺖو ﺣﻔﺎﻇﺖاﻳﻦ ﻗﺮاردادﻫﺎ را ﻓﺮاﻫﻢ ﻣﻲﻛﻨﺪ. در اﻳﻦ ﻣﻘﺎﻟﻪ، در آﻏﺎز ﺑﻪﻣﻌﺮﻓﻲ ﺗﺌﻮری رﻣﺰﮔﺬاری و در اداﻣﻪاﻧﻮاع روش ﻫﺎی ﻛﺪﮔﺬاریو ﻣﺘﺪﻫﺎی آن را ﺑﺮرﺳﻲﻣﻲ ﻛﻨﻴﻢ.

ﻣﺘﻦ ﻣﻘﺎﻟﻪ:

رﻣﺰﮔﺬاری ﻋﺒﺎرتاﺳﺖاز ﻓﺮاﻳﻨﺪﺗﻐﻴﻴﺮ ﺷﻜﻞ اﻃﻼﻋﺎت اﻟﻜﺘﺮوﻧﻴﻜﻲ در ﻳﻚ ﻓﺮم ﺧﺎص ﻛﻪﺗﻨﻬﺎ ﺗﻮﺳﻂ ﻳﻚ ﺷﺨﺺﻳﺎﻋﺪهایﺧﺎصﻗﺎﺑﻞ ﺧﻮاﻧﺪن وﺗﺮﺟﻤﻪ ﺷﺪن ﺑﺎﺷﺪ. ﺗﺌﻮریرﻣﺰﮔﺬاریﻳﺎ ﺗﺌﻮریرﻣﺰﻧﮕﺎری(Coding Theory)، ﻳﻚ ﺷﺎﺧﻪازﻋﻠﻮمﻛﺎﻣﭙﻴﻮﺗﺮو رﻳﺎﺿﻲ اﺳﺖﻛﻪﺑﺎ ﻓﺮاﻳﻨﺪﻫﺎیﻣﺘﻤﺎﻳﻞ ﺑﻪ ﺧﻄﺎ (Error-prone) از ﻃﺮﻳﻖ اﻧﺘﻘﺎل دادهﻫﺎدرﻛﺎﻧﺎل ﻫﺎی ارﺗﺒﺎﻃﻲ ﺷﻠﻮغ ﻛﺎر ﻣﻲ ﻛﻨﺪ. ﺑﻨﺎﺑﺮاﻳﻦ، ﺗﻌﺪاد ﺑﺴﻴﺎر زﻳﺎدیاز اﺷﺘﺒﺎﻫﺎتو ﺧﻄﺎﻫﺎﻳﻲ ﻛﻪدرﻛﺎﻧﺎل ﻫﺎی ارﺗﺒﺎﻃﻲ اﻳﺠﺎد ﻣﻲﺷﻮﻧﺪ، ﻗﺎﺑﻞ ﺗﺼﺤﻴﺢ و درﺳﺖﺷﺪن ﻣﻲ ﺑﺎﺷﻨﺪ. ﻫﻤﭽﻨﻴﻦ اﻳﻦ ﺗﺌﻮریﺑﺎ ﺧﺼﻮﺻﻴﺎتﻛﺪﻫﺎ و رﻣﺰﻫﺎ ارﺗﺒﺎط ﺑﺮﻗﺮار ﻣﻲ ﻛﻨﺪوآن ﻫﺎ را ﺑﺮایﻛﺎرﺑﺮد ﻣﻨﺎﺳﺐﺧﻮددر ﺟﺎیﻣﻨﺎﺳﺐراﻫﻨﻤﺎﻳﻲ وﻫﺪاﻳﺖﻣﻲ ﻛﻨﺪ. دو ﻃﺒﻘﻪﺑﻨﺪیازﻛﺪﻫﺎ و رﻣﺰﻫﺎ وﺟﻮددارد:

(Entropy Coding ﻳﺎ Source Coding ) ﻛﺪﮔﺬاریﻣﻨﺒﻊ (1

(Forward Error Correction ﻳﺎ Channel Co ding) ﻛﺪﮔﺬاریﻛﺎﻧﺎل (2

1( ﻛﺪﮔﺬاریﻣﻨﺒﻊ، ﺗﻼش ﻣﻲ ﻛﻨﺪﺗﺎ دادهﻫﺎ را ﺑﺼﻮرتﻓﺸﺮده (Compress) از ﻳﻚ ﻣﻨﺒﻊ در ﺑﻴﺎوردﺗﺎ ﺑﺘﻮاﻧﺪآن ﻫﺎ را ﺑﻪﺻﻮرتاﺛﺮﺑﺨﺶ (Efficient) اﻧﺘﻘﺎل دﻫﺪ. ﻣﺎ اﻳﻦ ﻋﻤﻞ راﻫﺮروز در اﻳﻨﺘﺮﻧﺖ،ﻫﻨﮕﺎﻣﻲ ﻛﻪدادهﻫﺎ را ﻓﺸﺮده ﻣﻲ ﺳﺎزﻳﻢ وﺣﺠﻢ ﻓﺎﻳﻞ ﻫﺎ راﻛﻤﺘﺮﻣﻲ ﻛﻨﻴﻢ، ﻣﺸﺎﻫﺪه ﻣﻲ ﻛﻨﻴﻢ. ﺑﺎ اﻳﻦ ﻛﺎر، ﺑﺎر ﺷﺒﻜﻪﻳﺎ ﺗﺮاﻓﻴﻚ آن (Network Load) راﻛﻤﺘﺮﺧﻮاﻫﻴﻢ ﻛﺮد.

2(ﻛﺪﮔﺬاریﻛﺎﻧﺎل، ﺑﻴﺖﻫﺎیداده ایراﻛﻪﺑﻴﺖﻫﺎیزاﺋﺪ(Redundant bits) ﻧﻴﺰ ﺧﻮاﻧﺪه ﻣﻲ ﺷﻮﻧﺪ، ﺑﺮای اﻧﺘﻘﺎل دادهﻫﺎ اﺿﺎﻓﻪﻣﻲ ﻛﻨﺪ. ﺑﺎ اﻳﻦ ﻛﺎر، اﻧﺘﻘﺎل دادهﻫﺎ درﻛﺎﻧﺎل ﻫﺎی ارﺗﺒﺎﻃﻲ ﺑﺎ ﻣﺰاﺣﻤﺖﻛﻤﺘﺮی ﻫﻤﺮاه ﺧﻮاﻫﺪ ﺷﺪ. ﺑﺮای ﻣﺜﺎل، ﻳﻚ CD ﻣﻮزﻳﻚ ﻣﻌﻤﻮﻟﻲ رادر ﻧﻈﺮﺑﮕﻴﺮﻳﺪ. اﻳﻦ CD از ﻳﻚ ﻛﺪﻗﻮیﺑﻪﻧﺎم(Reed-Solomon) اﺳﺘﻔﺎده ﻣﻲ ﻛﻨﺪﻛﻪﻣﺸﻜﻼتو ﺧﺮاﺑﻲ ﻫﺎیروی CD رادرﺳﺖﻣﻲ ﻧﻤﺎﻳﺪ.در اﻳﻦ ﻣﺜﺎل،ﻛﺎﻧﺎل ارﺗﺒﺎﻃﻲ ﻫﻤﺎن CD اﺳﺖ.

ﻣﻮدمﻫﺎی داده ای، وﺳﺎﻳﻞ ارﺗﺒﺎط ﺗﻠﻔﻨﻲ و ﺣﺘﻲ NASA (ﺳﺎزﻣﺎن ﻓﻀﺎﻧﻮردیاﻳﺎﻻتﻣﺘﺤﺪه آﻣﺮﻳﻜﺎ)، از روش ﻛﺪﮔﺬاریﻛﺎﻧﺎل ا ﺳﺘﻔﺎده ﺑﺴﻴﺎریﻣﻲ ﻛﻨﻨﺪ(www.wikipedia.org).

ﻫﻤﺎﻧﻄﻮرﻛﻪﺑﻴﺎن ﺷﺪ،ﻛﺪﮔﺬاریﻣﻨﺒﻊ، Entropy Coding ﻧﻴﺰ ﺧﻮاﻧﺪه ﻣﻲ ﺷﻮد. اﻣﺎ اﻧﺘﺮوﭘﻲ ﭼﻴﺴﺖ؟

اﻧﺘﺮوﭘﻲ ﻳﻚ ﻣﻨﺒﻊ،در واﻗﻊ اﻧﺪازهﮔﻴﺮی اﻃﻼﻋﺎت آن ﻣﻨﺒﻊ ﻣﻲ ﺑﺎﺷﺪ. ﺗﻜﻨﻴﻚ ﻫﺎی ﻣﺨﺘﻠﻔﻲ ﺑﺮای ﻛﺪﮔﺬاری ﻣﻨﺒﻊ وﺟﻮد دارﻧﺪﻛﻪ ﺣﺪاﻧﺘﺮوﭘﻲﻣﻨﺒﻊ را ﺗﻌﻴﻴﻦ ﻣﻲ ﻛﻨﻨﺪ. ﺑﺮایﻣﺜﺎل، اﮔﺮ(C(X ﺗﻌﺪادﺑﻴﺖرﻳﺖﻫﺎ (Bit rates) ﺑﻌﺪاز ﻓﺸﺮده ﺳﺎزیﺑﺎﺷﺪو (H(X