131 بررسی ﺗﺌﻮری رﻣﺰﮔﺬاری و راﺑﻄﻪ آن ﺑﺎ ﻋﻠﻢ ﻛﺎﻣﭙﻴﻮﺗﺮ 23 صفحه فایل ورد

ﭼﻜﻴﺪه:

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

ﻛﻠﻴﺪ واژه ﻫﺎ:

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

ﻣﻘﺪﻣﻪ:

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

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

ﻣﺘﻦ ﻣﻘﺎﻟﻪ:

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

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

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

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

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

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

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

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

اﻧﺘﺮوﭘﻲ ﻣﻨﺒﻊ ﺑﺎﺷﺪ، آﻧﮕﺎه :

ﺑﻨﺎﺑﺮاﻳﻦ اﻃﻼﻋﺎتﺑﻴﺸﺘﺮیﺑﻌﺪاز ﻓﺸﺮده ﺳﺎزیاﻧﺘﻘﺎل داده ﻣﻲ ﺷﻮد.

ﺗﺌﻮریﻛﺪﮔﺬاریﺟﺒﺮی(Algebric Coding Theory)، ﻳﻚ زﻳﺮﻣﺠﻤﻮﻋﻪاز ﺗﺌﻮریﻛﺪﻳﻨﮓ ﻣﺤـﺴﻮبﻣـﻲ ﺷـﻮدﻛـﻪﺧﺼﻮﺻﻴﺎتﻛﺪﻫﺎ را ﺑﻪ ﺻﻮرتﻋﺒﺎراتﺟﺒﺮیﺑﻴﺎن ﻣﻲ ﻛﻨﺪ. ﺗﺌﻮریﻛﺪﮔﺬاری ﺟﺒﺮی، ﺧﻮدﺑﻪدو دﺳﺘﻪﻛﺪاﺻـﻠﻲ ﺗﻘـﺴﻴﻢ

ﻣﻲ ﺷﻮد:

(Linear Block Codes) ﺳﺪﻛﻨﻨﺪه ﻛﺪﻫﺎیﺧﻄﻲ(1

(Convolutional Codes)ﻛﺪﻫﺎیﺣﻠﻘﻪای (2

ﺗﺌﻮریﻛﺪﮔﺬاریﺟﺒﺮی، ﺳﻪ ﺧﺼﻮﺻﻴﺖﻫﺮﻛﺪرا ﺑﺮرﺳﻲ وﺗﺠﺰﻳﻪﻣﻲ ﻛﻨﺪ:

a) ﻃﻮل ﻛﻠﻤﺎترﻣﺰ b) ﺗﻌﺪادﻛﻠﻲ ﻛﻠﻤﺎترﻣﺰیﻣﻌﺘﺒﺮc) ﺣﺪاﻗﻞ ﻓﺎﺻﻠﻪﺑﻴﻦ دوﻛﻠﻤﺎترﻣﺰیﻣﻌﺘﺒﺮاﻛﻨﻮن ﻣﻄﺎﻟﺒﻲ رادر ﻣﻮردﻛﺪﻫﺎیﺧﻄﻲ ﺳﺪﻛﻨﻨﺪه ﺑﻴﺎن ﺧﻮاﻫﻴﻢ ﻛﺮد. اﻳﻦ ﻛﺪﻫﺎ ﺧﺎﺻﻴﺖﺧﻄﻲ(Linearity)را دارﻧﺪ. ﺑﻪﻋﺒﺎرتدﻳﮕﺮ، ﻣﺠﻤﻮع ﻫﺮدوﻛﻠﻤﻪرﻣﺰ، ﻳﻚ ﻛﻠﻤﻪرﻣﺰ