(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 6.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 13472, 470] NotebookOptionsPosition[ 11394, 397] NotebookOutlinePosition[ 11899, 417] CellTagsIndexPosition[ 11856, 414] WindowFrame->Normal ContainsDynamic->False*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["Cyclic Redundancy Check (CRC) Example, Part 1", "Title", CellChangeTimes->{{3.429475765993868*^9, 3.429475767253709*^9}}, TextAlignment->Center, FontSize->16], Cell["Sean E. O'Connor", "Subtitle", CellMargins->{{7, Inherited}, {Inherited, Inherited}}, TextAlignment->Center, FontSize->18], Cell[TextData[StyleBox["artificer!AT!seanerikoconnor!DOT!freeservers!DOT!com",\ "Subsubtitle"]], "Subtitle", CellMargins->{{7, Inherited}, {Inherited, Inherited}}, TextAlignment->Center], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ". An Example with CRC-16" }], "Section", CellChangeTimes->{{3.4294791729576597`*^9, 3.429479173256295*^9}}, FontSize->16], Cell["The CRC-16 generator polynomial is", "Text"], Cell[BoxData[ RowBox[{ RowBox[{"g", " ", "=", " ", RowBox[{ SuperscriptBox["x", "16"], "+", SuperscriptBox["x", "15"], " ", "+", SuperscriptBox["x", "2"], "+", "1"}]}], ";"}]], "Input", CellChangeTimes->{3.429479175363392*^9}], Cell[TextData[{ "Let a sample message be ", Cell[BoxData[ FormBox[ SubscriptBox["0102", "16"], TraditionalForm]]], ", which we will encode as the coefficients of the polynomial," }], "Text"], Cell[BoxData[ RowBox[{ RowBox[{"i", " ", "=", " ", RowBox[{ SuperscriptBox["x", "8"], "+", "x"}]}], ";"}]], "Input", CellChangeTimes->{3.429479178226849*^9}], Cell[TextData[{ "Let's assume we are encoding the message bit stream ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["0", "Code"], "E", " ", "0000000105020063656", "E", " ", "74757261", " ", SubscriptBox["00", "16"]}], TraditionalForm]]], ". The binary digits will be the coefficients of our message polynomial \ i(x), with the least significant bit being the constant term of the \ polynomial:" }], "Text", CellChangeTimes->{{3.4262581261673737`*^9, 3.426258128387796*^9}, { 3.426258166046579*^9, 3.42625820105221*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"i", "=", " ", RowBox[{ SuperscriptBox["x", "123"], "+", SuperscriptBox["x", "122"], "+", SuperscriptBox["x", "121"], "+", SuperscriptBox["x", "88"], "+", SuperscriptBox["x", "82"], "+", SuperscriptBox["x", "80"], "+", SuperscriptBox["x", "73"], "+", SuperscriptBox["x", "62"], "+", SuperscriptBox["x", "61"], "+", SuperscriptBox["x", "57"], "+", SuperscriptBox["x", "56"], "+", SuperscriptBox["x", "54"], "+", SuperscriptBox["x", "53"], "+", SuperscriptBox["x", "50"], "+", SuperscriptBox["x", "48"], "+", SuperscriptBox["x", "46"], "+", SuperscriptBox["x", "45"], "+", SuperscriptBox["x", "43"], "+", SuperscriptBox["x", "42"], "+", SuperscriptBox["x", "41"], "+", SuperscriptBox["x", "38"], "+", SuperscriptBox["x", "37"], "+", SuperscriptBox["x", "36"], "+", SuperscriptBox["x", "34"], "+", SuperscriptBox["x", "30"], "+", SuperscriptBox["x", "29"], "+", SuperscriptBox["x", "28"], "+", SuperscriptBox["x", "26"], "+", SuperscriptBox["x", "24"], "+", SuperscriptBox["x", "22"], "+", SuperscriptBox["x", "21"], "+", SuperscriptBox["x", "20"], "+", SuperscriptBox["x", "17"], "+", SuperscriptBox["x", "14"], "+", SuperscriptBox["x", "13"], "+", SuperscriptBox["x", "8"]}]}], ";"}]], "Input", CellChangeTimes->{3.429479182229206*^9}], Cell["\<\ Enter the code's blocklength n and message length k, and compute the the \ number of parity bits n-k.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"n", "=", RowBox[{ SuperscriptBox["2", "15"], "-", "1"}]}]], "Input"], Cell[BoxData["32767"], "Output", CellChangeTimes->{3.426015369613703*^9, 3.429474629923295*^9, 3.4294750215902843`*^9, 3.429476196370823*^9, 3.4294794105388327`*^9}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"k", " ", "=", " ", RowBox[{"n", " ", "-", " ", "16"}]}]], "Input"], Cell[BoxData["32751"], "Output", CellChangeTimes->{3.4260153696812687`*^9, 3.4294746300657682`*^9, 3.42947502169543*^9, 3.429476196457109*^9, 3.429479410601412*^9}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"n", "-", "k"}]], "Input"], Cell[BoxData["16"], "Output", CellChangeTimes->{3.4260153697473183`*^9, 3.429474630180306*^9, 3.429475021793745*^9, 3.429476196538121*^9, 3.429479410684361*^9}] }, Open ]], Cell[TextData[{ "For systematic encoding, the parity is p(x) = [-", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", RowBox[{"i", "(", "x", ")"}]}], "]"}], TraditionalForm]]], " mod g(x) where we do modulo 2 arithmetic on the polynomial coefficients." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"p", "=", RowBox[{"PolynomialMod", "[", RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", "i"}], ",", " ", RowBox[{"{", RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"], Cell[BoxData[ RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "3"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"], "+", SuperscriptBox["x", "8"], "+", SuperscriptBox["x", "10"], "+", SuperscriptBox["x", "12"], "+", SuperscriptBox["x", "13"]}]], "Output", CellChangeTimes->{3.426015369870337*^9, 3.4294746303498774`*^9, 3.4294750218967237`*^9, 3.429476196625025*^9, 3.4294794107543087`*^9}] }, Open ]], Cell[TextData[{ "Writing the polynomial coefficients in binary we get the parity, 0011 0101 \ 1100 1111", Cell[BoxData[ FormBox[ SubscriptBox["", "2"], TraditionalForm]]], "=35CF", Cell[BoxData[ FormBox[ SubscriptBox["", "16"], TraditionalForm]]] }], "Text", CellChangeTimes->{{3.4294791921924877`*^9, 3.429479193527697*^9}}], Cell[TextData[{ "Compute the systematically encoded codeword \nc(x) = ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", RowBox[{"i", "(", "x", ")"}]}], TraditionalForm]]], " + p(x)." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"c", " ", "=", " ", RowBox[{"Expand", "[", " ", RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", "i"}], " ", "+", " ", "p"}], " ", "]"}]}]], "Input"], Cell[BoxData[ RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "2"], "+", SuperscriptBox["x", "3"], "+", SuperscriptBox["x", "6"], "+", SuperscriptBox["x", "7"], "+", SuperscriptBox["x", "8"], "+", SuperscriptBox["x", "10"], "+", SuperscriptBox["x", "12"], "+", SuperscriptBox["x", "13"], "+", SuperscriptBox["x", "24"], "+", SuperscriptBox["x", "29"], "+", SuperscriptBox["x", "30"], "+", SuperscriptBox["x", "33"], "+", SuperscriptBox["x", "36"], "+", SuperscriptBox["x", "37"], "+", SuperscriptBox["x", "38"], "+", SuperscriptBox["x", "40"], "+", SuperscriptBox["x", "42"], "+", SuperscriptBox["x", "44"], "+", SuperscriptBox["x", "45"], "+", SuperscriptBox["x", "46"], "+", SuperscriptBox["x", "50"], "+", SuperscriptBox["x", "52"], "+", SuperscriptBox["x", "53"], "+", SuperscriptBox["x", "54"], "+", SuperscriptBox["x", "57"], "+", SuperscriptBox["x", "58"], "+", SuperscriptBox["x", "59"], "+", SuperscriptBox["x", "61"], "+", SuperscriptBox["x", "62"], "+", SuperscriptBox["x", "64"], "+", SuperscriptBox["x", "66"], "+", SuperscriptBox["x", "69"], "+", SuperscriptBox["x", "70"], "+", SuperscriptBox["x", "72"], "+", SuperscriptBox["x", "73"], "+", SuperscriptBox["x", "77"], "+", SuperscriptBox["x", "78"], "+", SuperscriptBox["x", "89"], "+", SuperscriptBox["x", "96"], "+", SuperscriptBox["x", "98"], "+", SuperscriptBox["x", "104"], "+", SuperscriptBox["x", "137"], "+", SuperscriptBox["x", "138"], "+", SuperscriptBox["x", "139"]}]], "Output", CellChangeTimes->{ 3.42601536992869*^9, 3.4294746304500637`*^9, 3.4294750219921093`*^9, 3.429476196703074*^9, {3.4294794027135973`*^9, 3.429479410846746*^9}}] }, Open ]], Cell[TextData[{ "Compute the shifted syndrome s'(x) = [", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", RowBox[{"c", "(", "x", ")"}]}], "]"}], TraditionalForm]]], " mod g(x), modulo 2 on the polynomial coefficients. We should get zero." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"p", "=", RowBox[{"PolynomialMod", "[", RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", "c"}], ",", " ", RowBox[{"{", RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"], Cell[BoxData["0"], "Output", CellChangeTimes->{3.426015370000052*^9, 3.429474630581002*^9, 3.429475022099608*^9, 3.4294761967566023`*^9, 3.429479410947546*^9}] }, Open ]], Cell["Add error to the codeword.", "Text"], Cell[BoxData[ RowBox[{ RowBox[{"cerror1", " ", "=", " ", RowBox[{"c", " ", "+", " ", SuperscriptBox["x", "11"]}]}], ";"}]], "Input", CellChangeTimes->{3.4294793867116003`*^9}], Cell[TextData[{ "Compute the shifted syndrome s'(x) = [", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", RowBox[{"c", "(", "x", ")"}]}], "]"}], TraditionalForm]]], " mod g(x) modulo 2 on the polynomial coefficients. We should get a \ non-zero answer." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"s", "=", RowBox[{"PolynomialMod", "[", RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", "cerror1"}], ",", " ", RowBox[{"{", RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"], Cell[BoxData[ RowBox[{"1", "+", "x", "+", SuperscriptBox["x", "12"], "+", SuperscriptBox["x", "13"], "+", SuperscriptBox["x", "15"]}]], "Output", CellChangeTimes->{3.426015370135129*^9, 3.429474630927177*^9, 3.429475022450248*^9, 3.429476196905768*^9, 3.429479411043271*^9}] }, Open ]], Cell["\<\ On the other hand, if we add a multiple of a codeword, we won't see the \ error.\ \>", "Text"], Cell[BoxData[ RowBox[{ RowBox[{"cerror2", " ", "=", " ", RowBox[{"c", " ", "+", " ", RowBox[{ SuperscriptBox["x", "2"], " ", "g"}]}]}], ";"}]], "Input", CellChangeTimes->{3.429479395190263*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"s", "=", RowBox[{"PolynomialMod", "[", RowBox[{ RowBox[{ SuperscriptBox["x", RowBox[{"n", "-", "k"}]], " ", "cerror2"}], ",", " ", RowBox[{"{", RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"], Cell[BoxData["0"], "Output", CellChangeTimes->{3.426015370268168*^9, 3.429474631179858*^9, 3.429475022667555*^9, 3.429476197041037*^9, 3.429479411120689*^9}] }, Open ]] }, Open ]] }, Open ]] }, WindowSize->{987, 729}, WindowMargins->{{395, Automatic}, {137, Automatic}}, PrintingCopies->1, PrintingPageRange->{1, Automatic}, CellLabelAutoDelete->True, Magnification->1.25, FrontEndVersion->"6.0 for Mac OS X x86 (32-bit) (May 21, 2008)", StyleDefinitions->FrontEnd`FileName[{"Article"}, "Preprint.nb", CharacterEncoding -> "UTF-8"] ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[590, 23, 167, 3, 70, "Title"], Cell[760, 28, 131, 3, 49, "Subtitle"], Cell[894, 33, 189, 3, 47, "Subtitle"], Cell[CellGroupData[{ Cell[1108, 40, 167, 6, 82, "Section"], Cell[1278, 48, 50, 0, 32, "Text"], Cell[1331, 50, 248, 7, 38, "Input"], Cell[1582, 59, 198, 6, 32, "Text"], Cell[1783, 67, 169, 5, 38, "Input"], Cell[1955, 74, 542, 13, 51, "Text"], Cell[2500, 89, 1452, 40, 62, "Input"], Cell[3955, 131, 125, 3, 32, "Text"], Cell[CellGroupData[{ Cell[4105, 138, 98, 3, 38, "Input"], Cell[4206, 143, 169, 2, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[4412, 150, 93, 2, 33, "Input"], Cell[4508, 154, 168, 2, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[4713, 161, 49, 1, 33, "Input"], Cell[4765, 164, 164, 2, 33, "Output"] }, Open ]], Cell[4944, 169, 336, 10, 39, "Text"], Cell[CellGroupData[{ Cell[5305, 183, 249, 8, 70, "Input"], Cell[5557, 193, 464, 11, 70, "Output"] }, Open ]], Cell[6036, 207, 341, 11, 70, "Text"], Cell[6380, 220, 254, 9, 70, "Text"], Cell[CellGroupData[{ Cell[6659, 233, 219, 7, 70, "Input"], Cell[6881, 242, 1755, 48, 70, "Output"] }, Open ]], Cell[8651, 293, 325, 10, 70, "Text"], Cell[CellGroupData[{ Cell[9001, 307, 249, 8, 70, "Input"], Cell[9253, 317, 163, 2, 70, "Output"] }, Open ]], Cell[9431, 322, 42, 0, 70, "Text"], Cell[9476, 324, 188, 5, 70, "Input"], Cell[9667, 331, 339, 11, 70, "Text"], Cell[CellGroupData[{ Cell[10031, 346, 255, 8, 70, "Input"], Cell[10289, 356, 288, 6, 70, "Output"] }, Open ]], Cell[10592, 365, 104, 3, 70, "Text"], Cell[10699, 370, 211, 6, 70, "Input"], Cell[CellGroupData[{ Cell[10935, 380, 255, 8, 70, "Input"], Cell[11193, 390, 161, 2, 70, "Output"] }, Open ]] }, Open ]] }, Open ]] } ] *) (* End of internal cache information *)