ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

CRC

CRCCyclic Redundancy CheckĹȤϡΰǤ롣ѥƥå٤ʻȤߤȤʤäƤ롣

CRCϡӥåΥǡ򤢤¿༰dzä;򸡺ѤCRCȤơǡղäǤ롣¦ϡǡƱ¿༰dzڤ뤫ݤǸȯ򸡽Ф롣

Ѥ¿༰ϥӥåĹˤä뤬ɽŪʤΤȤX16+X12+X5+1롣¿༰dzȤȤϡmod 2ȤƤߤȤΥӥå10001000000100001dzȤȤǤ롣

CRCħ

  • ¾ξĹǤѥƥåĹ٤Ӥƹ⤤긡ǽϤĤȤġ
  • ǡϡ㡧HDLCѤƥˤե쥭֥ǥ֤ˤϥӥåȸθФŪȤCRCѤƤ롣
  • Ϥˤϥޥԥ塼ѤƱ桦ʤɤεǽȹ碌CRC黻¹Ԥ뤳Ȥ¿
    • ξ硢ޥԥ塼ν١ʥƥå׿ˤCRC黻¸ʬŪ礭ʳƤΤǡκŬϽפǤ롣
  • ¿༰dzä;򸡺ѤCRCȤѤ롣ѥƥå׻ʣˤʤ뤬Сȸʸ꤬椷ȯ븽ݡˤ˶

CRCλȤ

CRCΥǡ֥ånӥåȡˤϡӥåȡkӥåȡˤȸӥåȡn-kӥåȡˤ鹽롣

ϰ̤¿༰Ǽ¸롣

㡧1101Τ褦ʥӥåDϡ¿༰D(x)=X3+X2+1Τ褦ɽȤǤ롣

CRCˤ긡Фϡ¦ǥåҤȤĤ¿༰ɽCRC¿༰G(X)dz껻ξ;ӥåȤ³ϩФäơӥåȤղä줿ӥåȤ¿༰ɽΤG(X)dzڤ롣

㡧1101101dzäȤ11;꤬10ˤʤ롣1101θ10ղä̤110111101dzȡ1110;꤬0ˤʤ롣

ǡ¦ǤϼǡG(x)dz껻;0Ǥи꤬ʤȤ;0Ǥʤи꤬äȽꤹ*1

CRCα黻

㤨С¿༰G(X)=X3+X+1ΤȤǡӥåDФ;ϼΤ褦˹Ԥ롣

\{~DX^3+(R_2~X^2+R_1X+R_0)X~\}~\div~(X^3+X+1)

ΤȤξȾ;ϼ̤Ǥ롣

  • R_2~\oplus~D
  • ;R_1X^2+(R_0~\oplus~R_2~\oplus~D)X+(R_2~\oplus~D)

äơ;ηȿ;ηδطϼΤ褦ɽ롣Rii=0,1,2ˤϿǤ롣3Ĥ(*)֤

  • R_2'=R_1
  • R_1'=R_0~\oplus~R_2~\oplus~D
  • R_0'=R_2~\oplus~D

[]ǤդĹmΥǡб¿༰f(X)t¿༰G(X)dz黻ϡtԥեȥ쥸G(X)ιбեɥХåġˤˤäơmΥեȤǼ¹ԤǤ롣

CRCǤɸŪ¿༰ȤG(X)=X16+X12+X5+1Ȥ롣ΤȤnӥåȤΥǡD(0),D(1),,D(n-1)ФCRC黻ϡ(*)n󷫤֤Ȥ롣k=0,1,,n-1Ǥ롣3Ĥ(**)֤

  • R^{(k+1)}(i)=R^{(k)}(15)~\oplus~D(k)~(\equiv~Q^{(k)})i=0
  • R^{(k+1)}(i)=R^{(k)}(i-1)~\oplus~Q^{(k)}i=5,12
  • R^{(k+1)}(i)=R^{(k)}(i-1)i0,5,12

ǡR^{(0)}(15),~R^{(0)}(14),\cdots,R^{(0)}(0)ϵ;R^{(n)}(15),~R^{(n)}(14),\cdots,R^{(n)}(0)Ͽ;ʤ⼡η̤ηءˤؤ

CRCα黻ι®

Ǥ8ӥåȤΥޥԥ塼ΥץǼ¸뤳ȤȤƹͤ롣

XOR̿ܥե̿ˡ

(**)R^{(0)}R^{(n)}ؤѴXOR¾Ū¡̿ȥե̿ѤƱ黻ˡˤĤƹͤ롣XOR̿λѲǾȤʤ褦˥ե̿λͼͤФ褤

ñ̽ӥåȿ8ӥåȤΤȤXOR̿5ˤʤ롣

ޤե̿βϥޥԥ塼Υե̿εǽˤäưۤʤ롣㤨С1ӥåȱե/եȤˤ硢ñ̽ӥåȿ18ӥåȤˤơե̿β10դĤ

XOR̿ȥե̿β碌ƹθȡñ̽ӥåȿ18ӥåȤ8ӥåȤΤȤ˺ǤΨ褤Ҥ٤С1ӥåȤΤȤʥӥåȥꥢα黻ˤ٤ȡ4ܸΨ褯ʤäƤ롣

8080ˤ

Intel 8080ϡ㤨8080AʤɤޤˤǤμǤZ80,F-8Ʊ͡ˡ

ΤȤ쥸λȤƻϼ̤Ǥ롣

A쥸8ӥåȤΥǡ
B쥸;ι̤8ӥåȡRU
C쥸;̤8ӥåȡRL
D,E쥸쥸

ΤȤ르ꥺϼΤ褦ˤʤ롣黻ľA쥸ˤ8ӥåȤΥǡBC쥸ˤϵ;ǼƤΤȤ롣

  1. A쥸B쥸֤XOR黻Ԥη̤D쥸˳Ǽ롣
  2. D쥸Ƥ4ӥåȺեȤ̤D쥸θƤXOR黻롣η̤D쥸˳Ǽ롣
    • 1ӥåȺեȤ뤳Ȥ2ܤ뤳ȤƱͤʤΤǡǤ1ӥåȺե̿̿¹Ի֤ûû̿ǥե̿Ԥ롣
  3. D쥸Ƥ3ӥåȺեȤη̤E쥸˳Ǽ롣
  4. E쥸Ƥȥӥåȥѥ"1111 1000"16ʿF8ˤAND黻롣η̤C쥸XOR黻ơη̤B쥸˳Ǽ롣
  5. E쥸Ƥ1ӥåȺեȤˡӥåȥѥ"0000 1111"16ʿ0FˤAND黻Ԥη̤B쥸XOR黻Ԥη̤B쥸˳Ǽ롣
  6. E쥸Ƥȥӥåȥѥ"0000 0111"16ʿ07ˤAND黻Ԥơη̤D쥸ȤXOR黻Ԥη̤C쥸˳Ǽ롣
  7. ǽŪBC쥸Ƥ;ˤʤ롣B쥸̤8ӥåȡRUˡC쥸̤8ӥåȡRLˤб롣
    • BC쥸ƤΤޤ޼8ӥåȥǡФƤϵ;б롣äơ8ӥåȥǡФƤϡΥǡA쥸˥åȤơƱΥ르ꥺ¹ԤФ褤Τ褦ˤơϥǡбʬ֤̤BC쥸ƤϥǡФCRCǡˤʤ롣

ΥɤϾ嵭Υ르ꥺIntel 8080Υ֥˼ΤǤ롣ȥȤοϥ르ꥺβվ񤭤ֹбƤ롣

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
XRA B        ; AA XOR B
MOV D,A        ; DA
ADD A        ; ʲ4Թ碌ơA+A+A+A¨4AƱư
ADD A
ADD A
ADD A
XRA D        ; AA XOR D
MOV D,A        ; DA
RLC            ; ʲ3Թ碌ơA3ӥåȺե
RLC
RLC
MOV E,A        ; EA
ANI 0F8H    ; AA AND "1111 1000"A=Eξ֤Ǥα黻򤹤Τǡ쥸EФƹԤäƤ뤳ȤƱ
XRA C        ; AA XOR C
MOV B,A        ; BA
MOV A,E        ; AE
RLC            ; 1ӥåȺե
ANI 0FH        ; AA AND "0000 1111"
XRA B        ; AA XOR B
MOV B,A        ; BA
MOV A,E        ; AE
ANI 07H        ; AA AND "0000 0111"
XRA D        ; AA XOR D
MOV C,A        ; CA

M6800ˤ

ȥҤM6800ǤμǤMC6502Ʊ͡ˡ8080AӤȡM6800ϥ쥸ιۤʤΤǡΤ褦ξԤΥ쥸ȥꥢλȤб롣

8080AM6800
A쥸A쥸
B쥸JOYO+1쥸
C쥸JOYO쥸
D쥸B쥸
E쥸WORK쥸

ơ֥ååפˡ

ơ֥ååפȤϡơ֥뤬ǼƤ뱦üɥ쥹ؼξǡ쥸Ⱦ;쥸XOR黻η̤ơ֥ΥǥåȰפƤ뤫ɤĴ٤ơ⤷פƤФΤȤƤϤ롣

(**)R^{(0)}ξnӥåȤȲ(16-n)ӥåȤʬΥƼ谷ԤȥǡӥåȤȤXOR黻η̤Ф;黻ơ֥ååפˤơη̤Ȳ(16-n)ӥåȤȤXOR黻η̤;Ȥʤ롣

ˡϡCRC黻ξ硢ơ֥Ƥˤäƥơ֥ۤʤ롣ơ֥礭Сʤʤ롣ơ֥򾮤С¿ʤ롣äơơ֥礭ˤäƱ黻֤礭롣

ޤȤ

XOR̿ܥե̿ˡȥơ֥ååפˡӤ롣Ԥñ̽ӥåȿ8ӥåȤΤȤǤΨ褤ʤ18ӥåȤ˸ꤷȤˡԤԤ᤯Ǥ뤬̤礭ʤäƤޤäơŪʥǽǤԤͥƤȤ롣

ʸ

  • 1֤ʬܾ󵻽ѼԽ楼ߡڸԡۡ2006ս
  • إ󥿡ե1977ǯ2桡No.13


*1 HDLCǤϤ餫;򤹤٤1˥åȤѤƤΤǡǽ;0Ȥʤʤ黻δŪϤȤߤƱͤǤ