(* 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[     13689,        498]
NotebookOptionsPosition[     11364,        413]
NotebookOutlinePosition[     11868,        433]
CellTagsIndexPosition[     11825,        430]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Cyclic Redundancy Check (CRC) Example, Part 3", "Title",
 CellChangeTimes->{{3.429475765993868*^9, 3.429475767253709*^9}, 
   3.429476104588109*^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-32Q"
}], "Section",
 FontSize->16],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"g", " ", "=", 
  RowBox[{
   RowBox[{"(", 
    RowBox[{"x", " ", "+", " ", "1"}], ")"}], " ", 
   RowBox[{"(", 
    RowBox[{
     SuperscriptBox["x", "31"], "+", 
     SuperscriptBox["x", "23"], " ", "+", 
     SuperscriptBox["x", "22"], "+", 
     SuperscriptBox["x", "15"], "+", 
     SuperscriptBox["x", "14"], "+", 
     SuperscriptBox["x", "7"], "+", 
     SuperscriptBox["x", "4"], "+", 
     SuperscriptBox["x", "3"], "+", "1"}], ")"}]}]}]], "Input"],

Cell[BoxData[
 RowBox[{
  RowBox[{"(", 
   RowBox[{"1", "+", "x"}], ")"}], " ", 
  RowBox[{"(", 
   RowBox[{"1", "+", 
    SuperscriptBox["x", "3"], "+", 
    SuperscriptBox["x", "4"], "+", 
    SuperscriptBox["x", "7"], "+", 
    SuperscriptBox["x", "14"], "+", 
    SuperscriptBox["x", "15"], "+", 
    SuperscriptBox["x", "22"], "+", 
    SuperscriptBox["x", "23"], "+", 
    SuperscriptBox["x", "31"]}], ")"}]}]], "Output",
 CellChangeTimes->{3.4260153703352823`*^9, 3.429474631309647*^9, 
  3.429475022782016*^9, 3.429476201428653*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"g", " ", "=", " ", 
  RowBox[{"PolynomialMod", "[", " ", 
   RowBox[{
    RowBox[{"Expand", "[", " ", "g", " ", "]"}], ",", "2"}], " ", 
   "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", "x", "+", 
  SuperscriptBox["x", "3"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "8"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "16"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "24"], "+", 
  SuperscriptBox["x", "31"], "+", 
  SuperscriptBox["x", "32"]}]], "Output",
 CellChangeTimes->{3.4260153704022818`*^9, 3.429474631428694*^9, 
  3.429475022882032*^9, 3.429476201604376*^9}]
}, Open  ]],

Cell["Let a sample message be", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"i", " ", "=", " ", 
  RowBox[{
   SuperscriptBox["x", "8"], "+", "x"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"x", "+", 
  SuperscriptBox["x", "8"]}]], "Output",
 CellChangeTimes->{3.426015370530773*^9, 3.429474631536811*^9, 
  3.429475022980698*^9, 3.4294762016847057`*^9}]
}, Open  ]],

Cell["Enter the code's blocklength and message length.", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"n", "=", 
  RowBox[{
   SuperscriptBox["2", "32"], "-", "1"}]}]], "Input"],

Cell[BoxData["4294967295"], "Output",
 CellChangeTimes->{3.426015370586466*^9, 3.4294746316357403`*^9, 
  3.4294750230790873`*^9, 3.429476201778873*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"k", " ", "=", " ", 
  RowBox[{"n", " ", "-", " ", "32"}]}]], "Input"],

Cell[BoxData["4294967263"], "Output",
 CellChangeTimes->{3.4260153706530647`*^9, 3.429474631813991*^9, 
  3.429475023197731*^9, 3.4294762018621387`*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"n", "-", "k"}]], "Input"],

Cell[BoxData["32"], "Output",
 CellChangeTimes->{3.426015370719933*^9, 3.429474631923657*^9, 
  3.4294750232922783`*^9, 3.429476201951857*^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", "12"], "+", 
  SuperscriptBox["x", "13"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "16"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "23"], "+", 
  SuperscriptBox["x", "24"], "+", 
  SuperscriptBox["x", "25"]}]], "Output",
 CellChangeTimes->{3.4260153707853394`*^9, 3.429474632027725*^9, 
  3.429475023486785*^9, 3.42947620202383*^9}]
}, Open  ]],

Cell[TextData[{
 "Writing the polynomial coefficients in binary, we get\n0011 1100 0011 0111 \
0001 1100 1111",
 Cell[BoxData[
  FormBox[
   SubscriptBox["", "2"], TraditionalForm]]],
 "=03C371CF",
 Cell[BoxData[
  FormBox[
   SubscriptBox["", "16"], TraditionalForm]]]
}], "Text"],

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", "12"], "+", 
  SuperscriptBox["x", "13"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "16"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "23"], "+", 
  SuperscriptBox["x", "24"], "+", 
  SuperscriptBox["x", "25"], "+", 
  SuperscriptBox["x", "33"], "+", 
  SuperscriptBox["x", "40"]}]], "Output",
 CellChangeTimes->{3.426015370853397*^9, 3.429474632115115*^9, 
  3.4294750235998297`*^9, 3.429476202082487*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"s", "=", 
  RowBox[{"PolynomialMod", "[", 
   RowBox[{
    RowBox[{
     SuperscriptBox["x", 
      RowBox[{"n", "-", "k"}]], "  ", "c"}], ",", " ", 
    RowBox[{"{", 
     RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData["0"], "Output",
 CellChangeTimes->{3.426015370920087*^9, 3.429474632231204*^9, 
  3.429475023702263*^9, 3.429476202143593*^9}]
}, Open  ]],

Cell["Add error to the codeword.", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"cerror1", " ", "=", " ", 
  RowBox[{"c", " ", "+", " ", 
   SuperscriptBox["x", "11"]}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", "x", "+", 
  SuperscriptBox["x", "2"], "+", 
  SuperscriptBox["x", "3"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "8"], "+", 
  SuperscriptBox["x", "11"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "13"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "16"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "23"], "+", 
  SuperscriptBox["x", "24"], "+", 
  SuperscriptBox["x", "25"], "+", 
  SuperscriptBox["x", "33"], "+", 
  SuperscriptBox["x", "40"]}]], "Output",
 CellChangeTimes->{3.426015370987403*^9, 3.429474632342536*^9, 
  3.4294750237940598`*^9, 3.429476202208663*^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 a \
non-zero answer."
}], "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"p", "=", 
  RowBox[{"PolynomialMod", "[", 
   RowBox[{
    RowBox[{
     SuperscriptBox["x", 
      RowBox[{"n", "-", "k"}]], "  ", "cerror1"}], ",", " ", 
    RowBox[{"{", 
     RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "8"], "+", 
  SuperscriptBox["x", "10"], "+", 
  SuperscriptBox["x", "11"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "16"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "23"], "+", 
  SuperscriptBox["x", "25"], "+", 
  SuperscriptBox["x", "26"], "+", 
  SuperscriptBox["x", "31"]}]], "Output",
 CellChangeTimes->{3.426015371054677*^9, 3.429474632448666*^9, 
  3.429475023907979*^9, 3.42947620227848*^9}]
}, Open  ]],

Cell["\<\
On the other hand, if we add a multiple of a codeword, we won't see the \
error.\
\>", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"cerror2", " ", "=", " ", 
  RowBox[{"Expand", "[", " ", 
   RowBox[{"PolynomialMod", "[", " ", 
    RowBox[{
     RowBox[{"c", " ", "+", " ", 
      RowBox[{
       SuperscriptBox["x", "2"], " ", "g"}]}], ",", " ", "2"}], "]"}], 
   "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", "x", "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "8"], "+", 
  SuperscriptBox["x", "9"], "+", 
  SuperscriptBox["x", "10"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "13"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "18"], "+", 
  SuperscriptBox["x", "22"], "+", 
  SuperscriptBox["x", "23"], "+", 
  SuperscriptBox["x", "25"], "+", 
  SuperscriptBox["x", "26"], "+", 
  SuperscriptBox["x", "34"], "+", 
  SuperscriptBox["x", "40"]}]], "Output",
 CellChangeTimes->{3.426015371121285*^9, 3.4294746325598097`*^9, 
  3.429475024014237*^9, 3.429476202344656*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"p", "=", 
  RowBox[{"PolynomialMod", "[", 
   RowBox[{
    RowBox[{
     SuperscriptBox["x", 
      RowBox[{"n", "-", "k"}]], "  ", 
     RowBox[{"(", "cerror2", ")"}]}], ",", " ", 
    RowBox[{"{", 
     RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData["0"], "Output",
 CellChangeTimes->{3.426015371187986*^9, 3.429474632664391*^9, 
  3.4294750241204567`*^9, 3.429476202408429*^9}]
}, Open  ]]
}, Open  ]]
}, Open  ]]
},
WindowSize->{822, 592},
WindowMargins->{{Automatic, 278}, {-4, 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, 193, 4, 70, "Title"],
Cell[786, 29, 131, 3, 49, "Subtitle"],
Cell[920, 34, 189, 3, 47, "Subtitle"],
Cell[CellGroupData[{
Cell[1134, 41, 100, 5, 82, "Section"],
Cell[CellGroupData[{
Cell[1259, 50, 481, 14, 42, "Input"],
Cell[1743, 66, 540, 15, 42, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[2320, 86, 182, 5, 33, "Input"],
Cell[2505, 93, 509, 13, 38, "Output"]
}, Open  ]],
Cell[3029, 109, 39, 0, 32, "Text"],
Cell[CellGroupData[{
Cell[3093, 113, 107, 3, 38, "Input"],
Cell[3203, 118, 187, 4, 38, "Output"]
}, Open  ]],
Cell[3405, 125, 64, 0, 32, "Text"],
Cell[CellGroupData[{
Cell[3494, 129, 98, 3, 38, "Input"],
Cell[3595, 134, 152, 2, 33, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3784, 141, 93, 2, 33, "Input"],
Cell[3880, 145, 152, 2, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[4069, 152, 49, 1, 70, "Input"],
Cell[4121, 155, 142, 2, 70, "Output"]
}, Open  ]],
Cell[4278, 160, 336, 10, 70, "Text"],
Cell[CellGroupData[{
Cell[4639, 174, 249, 8, 70, "Input"],
Cell[4891, 184, 647, 17, 70, "Output"]
}, Open  ]],
Cell[5553, 204, 281, 10, 70, "Text"],
Cell[5837, 216, 254, 9, 70, "Text"],
Cell[CellGroupData[{
Cell[6116, 229, 219, 7, 70, "Input"],
Cell[6338, 238, 718, 19, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[7093, 262, 249, 8, 70, "Input"],
Cell[7345, 272, 139, 2, 70, "Output"]
}, Open  ]],
Cell[7499, 277, 42, 0, 70, "Text"],
Cell[CellGroupData[{
Cell[7566, 281, 124, 3, 70, "Input"],
Cell[7693, 286, 753, 20, 70, "Output"]
}, Open  ]],
Cell[8461, 309, 340, 11, 70, "Text"],
Cell[CellGroupData[{
Cell[8826, 324, 255, 8, 70, "Input"],
Cell[9084, 334, 637, 17, 70, "Output"]
}, Open  ]],
Cell[9736, 354, 104, 3, 70, "Text"],
Cell[CellGroupData[{
Cell[9865, 361, 275, 8, 70, "Input"],
Cell[10143, 371, 719, 19, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[10899, 395, 281, 9, 70, "Input"],
Cell[11183, 406, 141, 2, 70, "Output"]
}, Open  ]]
}, Open  ]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)