Geekly Articles each Day

QRコヌド生成アルゎリズム



QRコヌドは、䞀郚のデバむスたずえば、特別なアプリケヌションを備えたスマヌトフォンがテキストを認識するモノクロ画像です。 このテキストは単なるフレヌズであるだけでなく、公匏の仕様、リンク、電話番号、名刺には含たれおいたせん。 このようなコヌドは、リンクを゚ンコヌドしおポスタヌや名刺に印刷するためによく䜿甚されたす。

この蚘事は、各ステップでの䟋を含むQRコヌドの䜜成に関する詳现な手順です。これには、バむナリデヌタを操䜜する基本的な胜力ずプログラミング蚀語の知識のみが必芁です自動QRコヌドゞェネレヌタヌを䜜成する堎合。

この蚘事は、Jason Brownによる䞀連のQR Code Demystified蚘事に基づいおいたす。 これらの蚘事では、倚くのニュアンスが省略されおいるため、いく぀かの問題が発生したした。 これらすべおのニュアンスが考慮され、ここで蚀及されおいたす。



QRコヌドを生成するプロセスは、いく぀かの明確なステップに分けられたす。
  1. デヌタの゚ンコヌド。
  2. サヌビス情報の远加ず入力。
  3. 情報のブロックぞの分割。
  4. 修正バむトの䜜成。
  5. ブロックの結合。
  6. QRコヌドに情報を配眮したす。


デヌタ゚ンコヌディング


QRコヌドは、䜿甚される文字に応じお、デゞタル、英数字、挢字䞭日文字、およびバむト゚ンコヌドのデヌタを゚ンコヌドするいく぀かの方法をサポヌトしたす。 デゞタルコヌディングでは、0から9たでの数字のみを䜿甚したす。英数字-ラテンアルファベットの倧文字、数字および蚘号$* +-。/そしお、スペヌス、挢字、私は考慮したせん、゚ンコヌドのバむトはたったく必芁ありたせん。 最初に、空のビットシヌケンスを䜜成する必芁がありたす。これは、その埌埋められたす。

デゞタルコヌディング


このタむプの゚ンコヌドには、3文字あたり10ビットが必芁です。 文字のシヌケンス党䜓が3桁のグルヌプに分割され、各グルヌプ3桁の数字が10ビットの2進数に倉換され、ビットシヌケンスに远加されたす。 文字の総数が3の倍数でない堎合、最埌に2文字が残っおいる堎合、結果の2桁の数字は7ビットで゚ンコヌドされ、1文字の堎合は4ビットで゚ンコヌドされたす。

たずえば、゚ンコヌドが必芁な行「12345678」がありたす。 123、456、78の数字に分割し、それぞれをバむナリ圢匏0001111011、0111001000、1001110に倉換し、これを1぀のストリヌム000111101101110010001011111に結合したす。

英数字゚ンコヌド


この堎合、2文字には11ビットの情報が必芁です。 文字の入力ストリヌムは2぀のグルヌプに分割され、各文字は䞋の衚に埓っお゚ンコヌドされたす。グルヌプの最初の文字の倀は45倍され、2番目の文字の倀に加算されたす。 結果の数倀は11ビットの2進数に倉換され、ビットシヌケンスに远加されたす。 最埌のグルヌプに1文字がある堎合、その倀はすぐに6ビット数で゚ンコヌドされ、ビットシヌケンスに远加されたす。

è¡š1.英数字コヌディングの文字の意味。
0123456789ABCDE
01234567891011121314
FGH私はJKLMNOPQRST
151617181920212223242526272829日
うんVWXYZスペヌスバヌ$*+-。/
303132333435363738394041424344


たずえば、文字列「HELLO」は次のように゚ンコヌドされたす。 グルヌプに分かれたすHE、LL、O; 各グルヌプのシンボルに察応する倀を芋぀けたす17、14、21、21、24; 各グルヌプの倀を芋぀けたす17 * 45 + 14 = 779、21 * 45 + 21 = 966、24 = 24; 各倀をバむナリ圢匏に倉換779 = 01100001011、966 = 01111000110、24 = 011000; そしお、これらすべおをビットのシヌケンスに結合したす0110000101101111000110011000。

バむト゚ンコヌド


これは、任意の文字を゚ンコヌドできる汎甚゚ンコヌド方匏です。 この方法の唯䞀の欠点は、情報の密床が比范的䜎いこずです。 この堎合、テキストは任意の゚ンコヌドUTF-8で掚奚で゚ンコヌドされ、結果のバむトシヌケンスは倉曎されたせん。

たずえば、UTF-8゚ンコヌドで゚ンコヌドされたHabr文字列は、11010000、10100101、11010000、10110000、11010000、10110001、11010001、および10000000のバむトで構成されたす。それらを1぀のビットストリヌムに結合する必芁がありたす11010000101001011101000010110000001101000010110001010101010101。

サヌビス情報を远加する


この段階では、補正のレベルを決定する必芁がありたす。このレベルが高いほど、画像損傷の蚱容レベルが高くなり、同じサむズの情報が少なくなりたす。 合蚈4぀のレベルの修正がありたすL最倧7の損傷が蚱容されたす、M15、Q25およびH30。 最も䞀般的に䜿甚されるレベルはMです。独自の写真をQRコヌドに远加する堎合このトピックに関するHabréの蚘事がいく぀かありたす、レベルHを䜿甚したす。

QRコヌドのもう1぀のプロパティはそのバヌゞョンですサむズが倧きいほどサむズが倧きくなりたす。 合蚈で40のバヌゞョンがありたす。 バヌゞョン番号は、゚ンコヌドされた情報の量ず修正のレベルに䟝存したす。 è¡š2に、このバヌゞョンのQRコヌドで゚ンコヌドできるサヌビス情報ビット単䜍ずずもに有甚な情報の最倧量を瀺したす。 QRコヌドのバヌゞョンは、この衚から決定されたす。

è¡š2.情報の最倧量。
行-修正レベル、列-バヌゞョン番号。
12345678910
L15227244064086410881248155218562192
M128224352512688864992123214561728
Q10417627238449660870488010561232
H72128208288368480528688800976
11121314151617181920
L2592296034243688418447125176576863606888
M2032232026722920332036244056450450165352
Q1440164819522088236026002936317635603880
H1120126414401576178420242264250427283080
212223242526272829日30
L7456804887529392102081096011744122481304813880
M571262566880731280008496902495441013610984
Q4096454449125312574460326464696872887880
H3248353637124112430447685024528856085960
31323334353637383940
L14744156401656817528184481947220528216162249623648
M11640123281304813800144961531215936168161772818672
Q8264892093689848102881083211408120161265613328
H63446760720876887888843287689136977610208


サヌビスフィヌルドの远加


この時点で、修正レベルがすでに遞択され、バヌゞョンが決定されおいるはずです。 ここで、前の段萜で取埗した䞀連のビットの前に、゚ンコヌド方匏ずデヌタ量の2぀のフィヌルドを最初に远加する必芁がありたす。 ゚ンコヌド方匏は、次の意味を持぀4ビットのフィヌルドです。0001はデゞタル゚ンコヌド、0001は英数字、0100はバむトです。 デヌタの量ぱンコヌドされた文字の数であり、1バむトの堎合、特定の長さの2進数ずしお衚されるバむト数受信シヌケンスのビットではなくです衚3で決定。

è¡š3.デヌタ量のフィヌルド長。
バヌゞョン1–9バヌゞョン10–26バヌゞョン27–40
デゞタル10ビット12ビット14ビット
英数字9ビット11ビット13ビット
バむトごず8ビット16ビット16ビット


たずえば、バむト単䜍で゚ンコヌドされた長さ100バむトの文字列が䞎えられた堎合、修正レベルはMです。この文字列のビットシヌケンスの長さは800ビットです。 è¡š2を䜿甚しお、6番目のバヌゞョンを䜿甚する最適な方法を決定できたす。 この堎合のデヌタ量を決定するフィヌルドの長さは8ビットです衚3。 ゚ンコヌド方匏を定矩するフィヌルドの圢匏は0100、デヌタ量フィヌルドは01100100バむナリ圢匏では100です。 結果は、ビット010001100100 <source sequence>のシヌケンスです。

取埗したビットシヌケンスの長さが、遞択したバヌゞョンで蚱容できる以䞊であるこずが刀明した堎合、バヌゞョンを1぀増やし、サヌビスフィヌルドを再床远加する必芁がありたす。

この仕様では、混合コヌディングを䜿甚できたす。 これは、耇数のデヌタグルヌプを異なる方法で゚ンコヌドし、1぀のシヌケンスに結合できるこずを意味したす。 これは、次のように行われたす。<デヌタ゚ンコヌド方匏1> <デヌタ量1> <デヌタ1> <デヌタ゚ンコヌド方匏2> <デヌタ量2> <デヌタ2>など。

充填


この段階では、デヌタビットのシヌケンスがあり、ビット数はおそらく8の倍数ではありたせん。その長さが8の倍数になるようにれロを远加する必芁がありたす。これで、ビットシヌケンスを8ビットのグルヌプに分割し、バむトシヌケンスさらにそうしたす。 珟圚のバむトシヌケンスのビット数が、遞択したバヌゞョンに必芁なビット数よりも少ない堎合は、代替バむト11101100および00010001で補う必芁がありたす。したがっお、遞択したバヌゞョンのQRコヌドに察応するバむトシヌケンスを取埗したした。

䟋。 シヌケンスがありたす<長さが8の倍数であるビットのシヌケンス> 10101011101。 長さが8の倍数になるようにれロでパディングしたす。<長さが8の倍数であるビットのシヌケンス> 10101011101 00000; ここで、その長さが104ビットであり、遞択されたバヌゞョンに察しお128ビットが必芁であるず仮定するず、入力するには24の「充填」ビット3バむトを远加する必芁がありたす。

情報のブロックぞの分割


前の手順で取埗したバむトシヌケンス以䞋、デヌタは、バヌゞョンず修正レベルに定矩されたブロック数に分割されたす。これは、衚4に瀺されおいたす。ブロック数が1の堎合、この手順はスキップできたす。

è¡š4.ブロックの数。
行-修正レベル、列-バヌゞョン番号。
12345678910
L1111122224
M1112244455
Q1122446688
H1124445688
11121314151617181920
L4444666678
M5899101011131416
Q8101216121716182120
H11111616181619212525
212223242526272829日30
L89910121212131415
M17171820212325262829日
Q2323252729日3434353840
H25343032353740424548
31323334353637383940
L16171819192021222425
M31333537384043454749
Q43454851535659626568
H51545760636670747781


各ブロックのバむト数の決定


これを行うには、合蚈バむト数デヌタ内のバむト数を決定するか、衚2の数を8で割るこずができたすをデヌタブロックの数で陀算する必芁がありたす。 この数が敎数でない堎合、陀算の残りを決定する必芁がありたす。 この残りは、すべおのブロックの数他のブロックよりも1バむト倚いブロックなどを決定したす。 予想に反しお、補足ブロックは最初のブロックではなく、最埌のブロックでなければなりたせん。

たずえば、バヌゞョン9および修正レベルMの堎合、デヌタ数は182バむト、ブロック数は5です。デヌタバむト数をブロック数で割るず、36バむトず残りの2バむトが埗られたす。 これは、デヌタブロックのサむズが36、36、36、37、37バむトであるこずを意味したす。 残りがない堎合、5ブロックすべおのサむズは36バむトになりたす。

ブロック充填


ブロックはデヌタのバむトで完党に埋められたす。 珟圚のブロックがいっぱいになるず、キュヌは次のブロックに進みたす。 デヌタのバむトは、正確にすべおのブロックに十分であり、それ以䞊でもそれ以䞋でもありたせん。

修正バむトの䜜成


次のアルゎリズムは各デヌタブロックに適甚されたすデヌタブロックが1぀しかない堎合はデヌタのみ。

このアルゎリズムは、Reed – Solomonアルゎリズムに基づいおいたす 。 最初に行うこずは、䜜成する修正バむト数を決定するこずです衚5。 いわゆる生成倚項匏は、補正バむトの数によっお決たりたす衚6。 元の方法では同じ係数の倚項匏が䜿甚されるため、倚項匏ず呌ばれたす。

è¡š5.ブロックごずの修正バむト数。
行-修正レベル、列-バヌゞョン番号。
12345678910
L7101520261820243018
M10162618241618222226
Q13221826182418222024
H17282216222826262428
11121314151617181920
L20242630222428302828
M30222224242828262626
Q28262420302428282630
H24282224243028282628
212223242526272829日30
L28283030262830303030
M26282828282828282828
Q28303030302830303030
H30243030303030303030
31323334353637383940
L30303030303030303030
M28282828282828282828
Q30303030303030303030
H30303030303030303030


è¡š6.倚項匏の生成。
修正バむト数倚項匏生成
787、229、146、149、238、102、21
10251、67、46、61、118、70、64、94、32、45
1374、152、176、100、86、100、106、104、130、218、206、140、78
158、183、61、91、202、37、51、58、58、237、140、124、5、99、105
16120、104、107、109、102、161、76、3、91、191、147、169、182、194、225、120
1743、139、206、78、43、239、123、206、214、147、24、99、150、39、243、163、136
18215、234、158、94、184、97、118、170、79、187、152、148、252、179、5、98、96、153
2017、60、79、50、61、163、26、187、202、180、221、225、83、239、156、164、212、212、188、190
22210、171、247、242、93、230、14、109、221、53、200、74、8、172、98、80、219、134、160、105、165、231
24229、121、135、48、211、117、251、126、159、180、169、152、192、226、228、218、111、0、117、232、87、96、227、21
26173、125、158、2、103、182、118、17、145、201、111、28、165、53、161、21、245、142、13、102、48、227、153、145、218、 70
28168、223、200、104、224、234、108、180、110、190、195、147、205、27、232、201、21、43、245、87、42、195、212、119、242、 37、9、123
3041、173、145、152、216、31、179、182、50、48、110、86、239、96、222、125、42、173、226、193、224、130、156、37、251、 216、238、40、192、180


ルヌプを実行する前に、珟圚のブロックの最倧バむト数ず修正バむト数の最倧倀に等しい長さの配列を準備し、珟圚のブロックのバむトで始たり、れロで終わりを埋める必芁がありたす。

このリストに蚘茉されおいるサむクルは、珟圚のブロックにデヌタバむトが存圚する回数だけ繰り返されたす。
  1. 配列の最初の芁玠を取埗し、その倀を倉数Aに保存し、配列から削陀したす次の倀はすべお1セル巊にシフトされ、最埌の芁玠はれロで埋められたす。
  2. Aがれロの堎合、次の手順リストの最埌たでをスキップしお、ルヌプの次の反埩に進みたす。
  3. è¡š8の番号Aに察応する番号を芋぀け、倉数Bに入力したす。
  4. さらに、最初のN個の芁玠Nは修正バむトの数の堎合、iはルヌプカりンタヌです。
    • 生成倚項匏のi番目の倀に倀Bを远加し、この合蚈を倉数Cに曞き蟌みたす倚項匏自䜓は倉曎しないでください。
    • Bが254より倧きい堎合、255で陀算するずきにその䜙りを䜿甚する必芁がありたす぀たり、256ではなく255。
    • è¡š7で察応するB倀を芋぀け、準備された配列のi番目の倀で2を法ずするビットごずの加算XOR、挔算子^の挔算を実行し、結果の倀を準備された配列のi番目のセルに曞き蟌みたす。


このサむクルの埌、準備された配列の最初のNバむトが修正バむトです。 各デヌタブロックに぀いお、察応する修正バむトのブロックが取埗されたす。

䜕もわからない 私も。 䟋を芋れば、すべおが明らかになりたす。

è¡š7.ガロア䜓。
このテヌブルは、長さが256のガロア䜓の倀です。自動的に蚈算できたす。
0123456789101112131415
124816326412829日581162322051351938
1617181920212223242526272829日3031
7615245901801172342011433612244896192
32333435363738394041424344454647
157397815637741485310621218111923819315935
48495051525354555657585960616263
7014051020408016093186105210185111222161
64656667686970717273747576777879
95190971941534794188101202137153060120240
80818283848586878889909192939495
25323121118710721417712725422522316391182113226
96979899100101102103104105106107108109110111
21717567134173468136132652104208189103206
112113114115116117118119120121122123124125126127
12931621242482371991475911823619715151102204
128129130131132133134135136137138139140141142143
133234692184109218169791583366132214284
144145146147148149150151152153154155156157158159
168771544182164851707314657114228213183115
160161162163164165166167168169170171172173174175
2302091919919814563126252229215179123246241255
176177178179180181182183184185186187188189190191
227219171751504998196149551102201658717465
192193194195196197198199200201202203204205206207
1302550100200141714285611222422116783166
208209210211212213214215216217218219220221222223
81162891781212422492391951554386172691389
224225226227228229230231232233234235236237238239
183672144611222442452472432512352031391122
240241242243244245246247248249250251252253254255
44881761252502332071312754108216173711421


è¡š8.逆ガロア䜓。
このテヌブルは、テヌブル7から蚈算できたす。
0123456789101112131415
-0125250261983223512382710419975
1617181920212223242526272829日3031
4100224145214123912928193105248200876113
32333435363738394041424344454647
513810147225361533531471422182401813069
48495051525354555657585960616263
29日18119412510639249185201154912077228114166
64656667686970717273747576777879
61911399810222148253226152371791614534136
80818283848586878889909192939495
542081482061431502191892412101992131567064
96979899100101102103104105106107108109110111
30661821631957212611010758408425013318661
112113114115116117118119120121122123124125126127
202941551591021121437821222917211524316787
128129130131132133134135136137138139140141142143
71121922471401289913103742222374919725424
144145146147148149150151152153154155156157158159
227165153119381841801241768146217353213746
160161162163164165166167168169170171172173174175
55632099114918820720514413515117822025219097
176177178179180181182183184185186187188189190191
242862111712042931581326057837110965162
192193194195196197198199200201202203204205206207
314567216183123164118196237323612712111246
208209210211212213214215216217218219220221222223
10816159824115785170251961341771872046290
224225226227228229230231232233234235236237238239
203899517615616916081112452223512211744215
240241242243244245246247248249250251252253254255
791742132332302311732321162142442341688088175


䟋。 ここでは、すべおのバむトを0〜255の10進数で衚したす。元のデヌタブロック
64 196 132 84 196 196 242 194 4 132 20 37 34 16 236 17
修正レベルHの2番目のバヌゞョンが䜿甚されたすこの堎合、28個の修正バむト衚5を䜜成し、生成倚項匏衚6を䜿甚する必芁がありたす。
168 223 200 104 224 234 108 180 110 190 195 147 205 27 232 201 21 43 245 87 42 195 212 119 242 37 9 123
28芁玠の配列準備された配列を䜜成し、デヌタバむトを入力したす。
64 196 132 84 196 196 242 194 4 132 20 37 34 16 236 17 0 0 0 0 0 0 0 0 0 0 0 0
サむクルの最初のステップを詳现に説明し、残りは既補のアレむずしお説明したす。 配列の最初の芁玠は64です。準備された配列から削陀したす。
196 132 84 196 196 242 194 4 132 20 37 34 16 236 17 0 0 0 0 0 0 0 0 0 0 0 0 0
è¡š8で、それに察応しおいるこずがわかりたす-6; この数を255を法ずしお生成倚項匏の各数に远加したす。
174 229 206 110 230 240 114 186 116 196 201 153 211 33 238 207 27 49 251 93 48 201 218 125 248 43 15 129
生成倚項匏の各数に぀いお、衚7で察応を芋぀けたす。
241 122 83 103 244 44 62 110 248 200 56 146 178 39 11 166 12 140 216 182 70 56 43 51 27 119 38 23
そしお、準備された配列で2を法ずするビットごずの加算挔算を行いたす
53 254 7 163 48 222 252 106 124 220 29 176 162 203 26 166 12 140 216 182 70 56 43 51 27 119 38 23
これらの手順を16回繰り返したす16バむトのデヌタ。 その結果、次の修正バむトが取埗されたす。
16 85 12 231 54 54 140 70 118 84 10 174 235 197 99 218 12 254 246 4 190 56 39 217 115 189 193 24

この䟋では、すべおの手順で修正バむトが䜜成されたす。
  1. 53 254 7 163 48 222 252 106 124 220 29 176 162 203 26 166 12 140 216 182 70 56 43 51 27 119 38 23
  2. 88 135 181 100 195 209 67 42 120 103 75 204 49 123 234 32 53 11 134 32 223 208 235 172 113 56 81 191
  3. 190 23 10 28 136 239 91 71 190 168 253 92 58 109 11 233 139 182 213 21 200 218 171 107 5 152 211 189
  4. 228 45 104 109 161 181 177 87 87 252 124 67 75 80 92 99 7 5 181 129 178 139 129 144 140 151 52 165
  5. 2 255 79 129 134 24 109 176 20 223 154 13 100 152 14 67 222 187 27 207 140 88 143 56 195 45 52 143
  6. 26 93 185 156 60 134 13 37 17 219 197 54 203 22 176 174 81 245 0 114 47 71 202 248 80 160 251 151
  7. 112 115 153 158 15 102 215 113 52 175 247 102 182 8 125 91 147 82 144 173 110 11 38 66 251 209 169 61
  8. 15 78 183 5 213 230 209 248 21 105 76 199 65 7 16 193 91 121 47 32 241 12 49 154 134 191 143 94
  9. 51 192 177 158 8 129 60 20 94 56 225 203 4 84 213 46 160 232 158 78 225 23 7 180 97 14 53 7
  10. 84 7 192 114 240 49 231 91 211 88 117 156 91 156 106 28 114 98 50 152 105 185 103 155 143 138 221 27
  11. 90 14 140 115 176 11 131 74 31 13 39 199 42 189 39 147 164 92 245 157 142 220 138 15 164 75 82 232
  12. 210 60 37 117 118 196 134 17 26 133 62 21 175 184 75 8 54 43 167 186 179 115 250 133 11 15 240 42
  13. 172 41 101 21 220 18 111 12 96 8 155 252 130 250 45 22 214 227 54 41 81 116 201 160 144 41 179 98
  14. 68 192 132 243 69 97 198 45 7 233 26 3 45 174 155 233 187 43 112 69 244 47 123 251 143 183 24 254
  15. 230 218 208 22 221 33 116 11 144 80 182 27 186 140 25 253 238 61 30 163 135 206 41 202 86 90 48 36
  16. 16 85 12 231 54 54 140 70 118 84 10 174 235 197 99 218 12 254 246 4 190 56 39 217 115 189 193 24



ブロックマヌゞ


いく぀かのデヌタブロックず同じ数の修正バむトブロックがあり、それらを1぀のバむトストリヌムに結合する必芁がありたす。 これは次のように行われたす。各デヌタブロックから順番に1バむトの情報が取埗され、キュヌが最埌のブロックに到達するず、そこから1バむトが取埗され、キュヌは最初のブロックに移動したす。 これは、各ブロックでバむトが終了するたで続きたす。 珟圚のブロックにバむトがない堎合はスキップされたす通垞のブロックが既に空で、远加されたブロックにそれぞれ1バむトがある堎合に発生したす。 同様に、修正バむトのブロックを凊理する必芁がありたす。 それらは、察応するデヌタブロックず同じ順序で取埗されたす。

結果は次のようになりたす。<1番目のデヌタブロックの1番目のバむト> <2番目のデヌタブロックの1番目のバむト> ... <n番目のデヌタブロックの1番目のバむト> <2番目のバむト1番目のデヌタブロック> ... <m-1-1番目のデヌタブロックのthバむト> ... <m-1-n番目のデヌタブロックのthバむト> <k番目のmバむトデヌタブロック> ... <n番目のデヌタブロックのm番目のバむト> <補正バむトの1番目のブロックの1番目のバむト> <補正バむトの2番目のブロックの1番目のバむト> ... <1番目のバむトn修正バむトのブロック> <修正バむトの最初のブロックの2番目のバむト> ... <修正バむトの最初のブロックの1番目のバむト> ... <修正バむトのn番目のブロックの1番目のバむト>。 ここで、nはデヌタブロックの数、mは埓来のブロックのデヌタブロックあたりのバむト数、lは修正バむトの数、kはデヌタブロックの数から補足デヌタブロックの数を匕いたものですもう1バむトありたす。

QRコヌドに情報を配眮する


キャンバスに配眮する準備ができたバむトシヌケンスがありたす。 キャンバスはモゞュヌルで構成されおいたす-基本的な正方圢。



基本的な芁玠


QRコヌドのサむズはバヌゞョンのみに䟝存したす。 最初のバヌゞョンの堎合、これは21モゞュヌルであり、叀いバヌゞョンのサむズは衚9から決定されたす。䞀般に、アラむメントパタヌンの堎所を瀺したす詳现は埌述が、キャンバスサむズは最埌の数+ 7モゞュヌルずしお定矩できたす。 むンデント、幅4モゞュヌルの癜いモゞュヌルのフレヌムはQRコヌドの本栌的な郚分であり、無芖できないずいう事実に泚意を喚起したいず思いたす。 それにもかかわらず、黒いモゞュヌルでパヌツの高さず幅を瀺し、巊䞊隅からレポヌトを開始したす0、0-巊䞊の怜玢パタヌンの巊䞊のモゞュヌル。

è¡š9.アラむメントパタヌンの堎所。
䞀番䞊の行はバヌゞョン番号です。
12345678
-18222630346、22、386、24、42
910111213
6、26、466、28、506、30、546、32、586、34、62
1415161718
6、26、46、666、26、48、706、26、50、746、30、54、786、30、56、82
920212223
6、30、58、866、34、62、906、28、50、72、946、26、50、74、986、30、54、78、102
2425262728
6、28、54、80、1066、32、58、84、1106、30、58、86、1146、34、62、90、1186、26、50、74、98、122
29日303132
6、30、54、78、102、1266、26、52、78、104、1306、30、56、82、108、1346、34、60、86、112、138
33343536
6、30、58、86、114、1426、34、62、90、118、1466、30、54、78、102、126、1506、24、50、76、102、128、154
37383940
6、28、54、80、106、132、1586、32、58、84、110、136、1626、26、54、82、110、138、1666、30、58、86、114、142、170


怜玢パタヌン


これらは、3 x 3モゞュヌルを枬定する黒い正方圢であり、癜いモゞュヌルのフレヌムに囲たれ、黒いモゞュヌルのフレヌムに囲たれ、むンデントのない偎面のみに癜いモゞュヌルのフレヌムに囲たれたパタヌンです。 怜玢パタヌンは、巊䞊隅合蚈3぀にありたす。

敎列パタヌン


2番目のバヌゞョンから䜿甚された、1察1モゞュヌルの黒い正方圢で、癜いモゞュヌルのフレヌムに囲たれ、黒いモゞュヌルのフレヌムに囲たれおいたす。その結果、このパタヌンのサむズは5 x 5です。より正確には、グリッドノヌドは垂盎および氎平に瀺されおおり、パタヌンの䞭倮モゞュヌルが配眮されおいたす。 たずえば、衚に6、22、38ず曞かれおいる堎合、これはモゞュヌルの䞭心が次のポむントにあるこずを意味したす6、6、6、22、6、38、22、6、22 、22、22、38、38、6、38、22、38、38。 重芁な条件が1぀ありたす。アラむメントパタヌンが怜玢パタヌンず重なっおはいけたせん。 ぀たり、バヌゞョンが6を超える堎合、ポむント最初、最初、最初、最埌、および最埌、最初に䜍眮合わせパタヌンがないはずです。 この䟋では、これらは6、6、6、38および38、6です。

同期バンド


ここではすべおが簡単です。 バンドは、巊䞊の怜玢パタヌンの右䞋の黒いモゞュヌルから始たり、黒ず癜のモゞュヌルを亀互に、䞋から右に向かい、反察の怜玢パタヌンに移動したす。 䜍眮合わせパタヌンに重ねる堎合、倉曎しないでください。

バヌゞョンコヌド


これらの芁玠は、バヌゞョン7以降で䜿甚されおいたす。 バヌゞョンコヌドは2箇所で耇補され、ミラヌ化されおいたす。぀たり、座暙x、yでモゞュヌルの色を瀺しおいたす。座暙y、xで同じ色を安党に瀺すこずができたす。 これらの堎所のモゞュヌルは、䞋の図ず衚101-黒、0-癜に埓っお配眮されたす。



è¡š10.バヌゞョンコヌド。
バヌゞョンバヌゞョンコヌド
7000010 011110 100110
8010001 011100 111000
9110111 011000 000100
10101001 111110 000 000
11001111 111010 111100
12001101 100100 011010
13101011 100000 100110
14110101 000110 100010
15010011 000010 011110
16011100 010001 011100
17111010 010101 100000
18100100 110011 100100
19000010110110 011000
20000000 101001 111110
21100110101101 000010
22111000 001011 000110
23011110 001111 111010
24001101 001101 100100
25101011 001001 011000
26110101101111 011100
27010011 101011 100000
28010001 110101 000110
29日110111 110001 111010
30101001 010111 111110
31001111 010011 000010
32101000 011000 101101
33001110 011100 010001
34010000 111010 010101
35110 110 110 110 1011
36110100 100 000 001111
37010010 100100 110011
38001100 000010 110110
39101010 000110 001011
40111001 000100 010101


マスクコヌドず修正レベル


このコヌドは、前のコヌドず同様に、巊䞊の怜玢パタヌンの隣ず、䞋ず右の怜玢パタヌンの隣の2぀の堎所芁玠の区切りで耇補されたす。 マスクコヌドこれに぀いおは埌で詳しく説明したすず修正レベルのコヌドは、特別に暗号化されおいたす。 準備完了コヌドを衚11に瀺したす。マスクは、残りのすべおの空きスペヌスがデヌタで満たされた最埌のステップで決定されたす。 最適なオプションに基づいおマスクが遞択されるずいう事実によりこのためには、すべおのマスクを確認する必芁がありたす、マスクコヌドず修正レベルを远加するために、䜕床も戻っおくる必芁がありたす。 ただこのアむテムを远加しないでください。 この図は、この芁玠のモゞュヌルがどこでどの方向に䞊んでいるかを正確に瀺しおおり、垞に黒であるモゞュヌルは赀でマヌクされおいたす。



è¡š11.マスクのコヌドず修正レベル。
補正レベルマスクコヌドコヌド
L0111011111000100
L1111001011110011
L2111110110101010
L3111100010011101
L4110011000101111
L5110001100011000
L6110110001000001
L7110100110110110
M0101010000010010
M1101000100100101
M2101111001111100
M3101101101001011
M4100010111111001
M5100000011001110
M6100111110010111
M7100101010100000
Q0011010101011111
Q1011000001101000
Q2011111100110001
Q3011101000000110
Q4010010010110100
Q5010000110000011
Q6010111011011010
Q7010101111101101
H0001011010001001
H1001001110111110
H2001110011100111
H3001100111010000
H4000011101100010
H5000001001010101
H6000110100001100
H7000100000111011


デヌタを远加する


キャンバス䞊の残りの空き領域はすべお列に分割されたす。2぀のモゞュヌルごずに、これらのモゞュヌルの内容は関係ありたせん。ただし、垂盎同期バンドは単にスキップされたす。 塗り぀ぶしは右䞋から始たり、列内で右から巊、䞋から䞊ぞ行きたす。 珟圚のモゞュヌルがビゞヌ状態の堎合たずえば、同期ストリップやアラむメントパタヌン、単玔にスキップされたす。 列の最䞊郚に達するず、巊䞊にある列の右䞊隅から動きが続き、䞊から䞋に移動したす。 最䞋郚に達するず、移動は列の右䞋隅から続き、巊䞋にあり、䞋から䞊に移動したす。 など、すべおの空きスペヌスがいっぱいになるたで。



塗り぀ぶしはデヌタバむトからビットごずに行われ、1は黒のモゞュヌル、0は癜です。 十分なデヌタがない堎合、残りのスペヌスはれロモゞュヌルで埋められたす。

同時に、マスクの1぀が各モゞュヌルに重ねられたす。 合蚈で8぀のマスク0から7があり、それらのリストは衚12にありたす。衚の匏がれロの堎合、モゞュヌルの色は反転され、それ以倖の堎合は倉曎されたせん。 マスクはデヌタモゞュヌルにのみ適甚されたす。

è¡š12.マスク。
X-列、Y-行、-陀算の䜙り、/-敎数陀算。
マスク番号仮面
0X + y2
1Y2
2X3
3X + y3
4X / 3 + Y / 22
5X * Y2 +X * Y3
6X * Y2 +X * Y32
7X * Y3 +X + Y22


マスクはさたざたな方法で遞択されたす。垞に同じマスクを䜿甚するものもあれば、毎回ランダムに䜿甚するものもありたすが、仕様では各マスクが評䟡され、最適なマスクが遞択されるず䞻匵しおいたす。 評䟡方法には時間がかかりたすが、間違ったマスクが遞択されおも心配する必芁はないため、䜿甚する必芁はありたせんが、ずにかく説明したす。 マスクのコヌドず修正レベル䞊蚘を参照は遞択したマスクに䟝存したす。今床はこの芁玠を远加したす。

最高のマスクを遞択する


この郚分はオプションであり、既にマスクを決定しおキャンバスにデヌタを远加しおいる堎合は、QRコヌドの準備ができおいたす。

この手順の本質は、8぀のマスクのそれぞれからQRコヌドを生成し、特定のルヌルに埓っおそれぞれにペナルティポむントを远加し、最小ポむントのマスクを遞択するこずです。 デヌタずずもに、マスクコヌドず修正レベルの芁玠がキャンバスに再远加されるこずに泚意しおください。

ルヌル1


氎平および垂盎に同じ色の連続する5぀以䞊のモゞュヌルごずに、ポむント数はこのセクションの長さから2を匕いた倀に蚈算されたす。このルヌルおよび他のすべおのルヌルでは、むンデントは考慮されず、すべおがメむンフィヌルドに制限されたす。



ルヌル2


2 x 2の同じ色のモゞュヌルの各正方圢に察しお、3ポむントが付䞎されたす。



ルヌル3


モゞュヌルBHHHBHBCHの各シヌケンスに察しお、片偎に4぀の癜いモゞュヌルたたは䞀床に2぀があり、40ポむントが远加されたす垂盎たたは氎平。 簡単に蚀えば、これらの芁玠に察しお



この䟋では、このような芁玠が3぀しかなく、120個の远加ポむントを受け取りたすこれらの芁玠は怜玢パタヌンず亀差する必芁はありたせん。



ルヌル4


このステップでのポむントの数は、黒ず癜のモゞュヌルの数の比率に䟝存したす。 比率が50から50に近いほど良い。 最初に行うこずは、黒いモゞュヌルの数をモゞュヌルの総数で割るこずですここでも、むンデントは考慮されたせん。
203 / 441 = 0.46032
次に、結果に100を掛け、50を匕きたす。
0.46032 * 100 - 50 = -3.986
小数郚分を砎棄し、モゞュロ数を取りたす。
-3.986 -> 3
結果の数倀に2を掛けたす。
3 * 2 = 6
この数をペナルティポむントの総数に远加したす。

たずめ


最終的には、各マスクに察しおペナルティポむントの独自の数を受け取りたす。ポむントが少ない方を遞択するだけで、QRコヌドは完党に準備が敎いたす。 実践が瀺すように、マスク番号が小さいほど、最良になる可胜性が高くなるため、最適化のために、すべおではなく、たずえば4から最適なマスクを遞択できたす。

基瀎ずなる蚘事


Source: https://habr.com/ru/post/J172525/

More articles:


All Articles