(* 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[     12522,        464]
NotebookOptionsPosition[     10238,        381]
NotebookOutlinePosition[     10743,        401]
CellTagsIndexPosition[     10700,        398]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Cyclic Redundancy Check (CRC) Example, Part 2", "Title",
 CellChangeTimes->{{3.429475969456871*^9, 3.4294759718352947`*^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-CCITT"
}], "Section",
 FontSize->16],

Cell["The CRC-CCITT generator polynomial is", "Text"],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"g", " ", "=", " ", 
  RowBox[{
   SuperscriptBox["x", "16"], "+", 
   SuperscriptBox["x", "12"], " ", "+", 
   SuperscriptBox["x", "5"], "+", "1"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "16"]}]], "Output",
 CellChangeTimes->{3.426015371256257*^9, 3.429474632866589*^9, 
  3.4294750242110863`*^9, 3.429476199322013*^9}]
}, Open  ]],

Cell[TextData[{
 "Let's assume we are encoding the message bit stream ",
 Cell[BoxData[
  FormBox[
   RowBox[{"00050400", " ", 
    SubscriptBox["10", "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.426258209972637*^9, 3.426258211397581*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"i", "=", " ", 
  RowBox[{
   SuperscriptBox["x", "26"], "+", 
   SuperscriptBox["x", "24"], "+", 
   SuperscriptBox["x", "18"], "+", 
   SuperscriptBox["x", "4"], "+", "x"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"x", "+", 
  SuperscriptBox["x", "4"], "+", 
  SuperscriptBox["x", "18"], "+", 
  SuperscriptBox["x", "24"], "+", 
  SuperscriptBox["x", "26"]}]], "Output",
 CellChangeTimes->{3.426015371318693*^9, 3.429474632979465*^9, 
  3.4294750243198833`*^9, 3.429476199466118*^9}]
}, Open  ]],

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.426015371388969*^9, 3.42947463307998*^9, 
  3.4294750245091877`*^9, 3.429476199510611*^9}]
}, Open  ]],

Cell[CellGroupData[{

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

Cell[BoxData["32751"], "Output",
 CellChangeTimes->{3.426015371456757*^9, 3.429474633181905*^9, 
  3.429475024616351*^9, 3.4294761995972967`*^9}]
}, Open  ]],

Cell[CellGroupData[{

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

Cell[BoxData["16"], "Output",
 CellChangeTimes->{3.426015371584717*^9, 3.4294746332831182`*^9, 
  3.4294750247166986`*^9, 3.429476199657547*^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[{"x", "+", 
  SuperscriptBox["x", "2"], "+", 
  SuperscriptBox["x", "4"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "9"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "14"]}]], "Output",
 CellChangeTimes->{3.426015371638476*^9, 3.429474633382826*^9, 
  3.429475024821904*^9, 3.429476199726108*^9}]
}, Open  ]],

Cell[TextData[{
 "Writing the polynomial coefficients in binary we get the parity,\n0101 0011 \
1111 0110",
 Cell[BoxData[
  FormBox[
   SubscriptBox["", "2"], TraditionalForm]]],
 "=53F5",
 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[{"x", "+", 
  SuperscriptBox["x", "2"], "+", 
  SuperscriptBox["x", "4"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "9"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "20"], "+", 
  SuperscriptBox["x", "34"], "+", 
  SuperscriptBox["x", "40"], "+", 
  SuperscriptBox["x", "42"]}]], "Output",
 CellChangeTimes->{3.426015371689355*^9, 3.429474633473024*^9, 
  3.4294750249190903`*^9, 3.42947619979819*^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.426015371755828*^9, 3.4294746335686417`*^9, 
  3.429475025020831*^9, 3.429476199851624*^9}]
}, Open  ]],

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

Cell[CellGroupData[{

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

Cell[BoxData[
 RowBox[{"x", "+", 
  SuperscriptBox["x", "2"], "+", 
  SuperscriptBox["x", "4"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "9"], "+", 
  SuperscriptBox["x", "11"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "20"], "+", 
  SuperscriptBox["x", "34"], "+", 
  SuperscriptBox["x", "40"], "+", 
  SuperscriptBox["x", "42"]}]], "Output",
 CellChangeTimes->{3.426015371824407*^9, 3.429474633663003*^9, 
  3.42947502511939*^9, 3.42947619991789*^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[{"s", "=", 
  RowBox[{"PolynomialMod", "[", 
   RowBox[{
    RowBox[{
     SuperscriptBox["x", 
      RowBox[{"n", "-", "k"}]], "  ", "cerror1"}], ",", " ", 
    RowBox[{"{", 
     RowBox[{"g", ",", "2"}], "}"}]}], "]"}]}]], "Input"],

Cell[BoxData[
 RowBox[{"1", "+", 
  SuperscriptBox["x", "3"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "8"], "+", 
  SuperscriptBox["x", "11"], "+", 
  SuperscriptBox["x", "15"]}]], "Output",
 CellChangeTimes->{3.42601537189005*^9, 3.429474633766766*^9, 
  3.4294750252339697`*^9, 3.429476199987026*^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[{"c", " ", "+", " ", 
   RowBox[{
    SuperscriptBox["x", "2"], " ", "g"}]}]}]], "Input"],

Cell[BoxData[
 RowBox[{"x", "+", 
  SuperscriptBox["x", "2"], "+", 
  SuperscriptBox["x", "4"], "+", 
  SuperscriptBox["x", "5"], "+", 
  SuperscriptBox["x", "6"], "+", 
  SuperscriptBox["x", "7"], "+", 
  SuperscriptBox["x", "9"], "+", 
  SuperscriptBox["x", "12"], "+", 
  SuperscriptBox["x", "14"], "+", 
  SuperscriptBox["x", "17"], "+", 
  SuperscriptBox["x", "20"], "+", 
  SuperscriptBox["x", "34"], "+", 
  SuperscriptBox["x", "40"], "+", 
  SuperscriptBox["x", "42"], "+", 
  RowBox[{
   SuperscriptBox["x", "2"], " ", 
   RowBox[{"(", 
    RowBox[{"1", "+", 
     SuperscriptBox["x", "5"], "+", 
     SuperscriptBox["x", "12"], "+", 
     SuperscriptBox["x", "16"]}], ")"}]}]}]], "Output",
 CellChangeTimes->{3.426015371954215*^9, 3.4294746339614363`*^9, 
  3.42947502534136*^9, 3.429476200054351*^9}]
}, Open  ]],

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.426015372025826*^9, 3.42947463408384*^9, 
  3.429475025532189*^9, 3.42947620012278*^9}]
}, Open  ]]
}, Open  ]]
}, Open  ]]
},
WindowSize->{822, 592},
WindowMargins->{{Automatic, 151}, {Automatic, 236}},
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, 169, 3, 70, "Title"],
Cell[762, 28, 131, 3, 49, "Subtitle"],
Cell[896, 33, 189, 3, 47, "Subtitle"],
Cell[CellGroupData[{
Cell[1110, 40, 102, 5, 82, "Section"],
Cell[1215, 47, 53, 0, 32, "Text"],
Cell[CellGroupData[{
Cell[1293, 51, 184, 5, 38, "Input"],
Cell[1480, 58, 257, 6, 38, "Output"]
}, Open  ]],
Cell[1752, 67, 416, 10, 51, "Text"],
Cell[CellGroupData[{
Cell[2193, 81, 210, 6, 38, "Input"],
Cell[2406, 89, 292, 7, 38, "Output"]
}, Open  ]],
Cell[2713, 99, 125, 3, 32, "Text"],
Cell[CellGroupData[{
Cell[2863, 106, 98, 3, 38, "Input"],
Cell[2964, 111, 144, 2, 33, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3145, 118, 93, 2, 33, "Input"],
Cell[3241, 122, 145, 2, 33, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3423, 129, 49, 1, 70, "Input"],
Cell[3475, 132, 144, 2, 70, "Output"]
}, Open  ]],
Cell[3634, 137, 336, 10, 70, "Text"],
Cell[CellGroupData[{
Cell[3995, 151, 249, 8, 70, "Input"],
Cell[4247, 161, 425, 11, 70, "Output"]
}, Open  ]],
Cell[4687, 175, 273, 10, 70, "Text"],
Cell[4963, 187, 254, 9, 70, "Text"],
Cell[CellGroupData[{
Cell[5242, 200, 219, 7, 70, "Input"],
Cell[5464, 209, 601, 16, 70, "Output"]
}, Open  ]],
Cell[6080, 228, 325, 10, 70, "Text"],
Cell[CellGroupData[{
Cell[6430, 242, 249, 8, 70, "Input"],
Cell[6682, 252, 141, 2, 70, "Output"]
}, Open  ]],
Cell[6838, 257, 42, 0, 70, "Text"],
Cell[CellGroupData[{
Cell[6905, 261, 124, 3, 70, "Input"],
Cell[7032, 266, 633, 17, 70, "Output"]
}, Open  ]],
Cell[7680, 286, 339, 11, 70, "Text"],
Cell[CellGroupData[{
Cell[8044, 301, 255, 8, 70, "Input"],
Cell[8302, 311, 358, 9, 70, "Output"]
}, Open  ]],
Cell[8675, 323, 104, 3, 70, "Text"],
Cell[CellGroupData[{
Cell[8804, 330, 148, 4, 70, "Input"],
Cell[8955, 336, 811, 23, 70, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[9803, 364, 255, 8, 70, "Input"],
Cell[10061, 374, 137, 2, 70, "Output"]
}, Open  ]]
}, Open  ]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)