/usr/share/mozart/doc/fst/node3.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3 Generating Hamming Codes</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node2.html#fset.examples.steiner"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node4.html#fset.examples.binpacking">Next >></A></TD></TR></TABLE><DIV id="fset.examples.hamming"><H1><A name="fset.examples.hamming">3 Generating Hamming Codes</A></H1><P class="margin">Problem Specification</P><P> Generate a Hamming code that fits in <IMG alt="b" src="latex40.png">-bit words to code <IMG alt="n" src="latex30.png"> symbols where the Hamming distance between every two symbol codes is at least <IMG alt="d" src="latex41.png">. The Hamming distance between to words is the number of bit positions where they differ. </P><P class="margin">Model</P><P> A <IMG alt="b" src="latex40.png">-bit word is modeled by a set <IMG alt=" s \subseteq \{1,\ldots,b\}" src="latex42.png"> where <IMG alt="e \in s" src="latex43.png"> means that the bit at position <IMG alt="e" src="latex44.png"> is set (resp. unset otherwise). The <EM>Hamming distance</EM> <IMG alt="h(a,b)" src="latex45.png"> between two words <IMG alt="a" src="latex46.png"> and <IMG alt="b" src="latex40.png"> represented as sets <IMG alt="s_a" src="latex47.png"> and <IMG alt="s_b" src="latex48.png"> can be computed by subtracting from the word size <IMG alt="b" src="latex40.png"> the number of elements that is contained (<IMG alt="\#(s_a \cap s_b)" src="latex49.png">) resp. is not contained (<IMG alt="\#(\{1,\ldots,b\}\backslash (s_a \cup s_b))" src="latex50.png">) in both sets. Thus, the Hamming distance results in </P><BLOCKQUOTE><P><IMG alt="h(a,b) = b - \#(s_a \cap s_b) - \#(\{1,\ldots,b\}\backslash (s_a \cup
s_b))." src="latex51.png"></P></BLOCKQUOTE><P> </P><P class="margin">Solver</P><P> The function <CODE>Hamming</CODE> returns a solver to generate a Hamming code for <CODE>NumSymbols</CODE> symbols in words with <CODE>Bits</CODE> bits and a Hamming distance of <CODE>Distance</CODE>. The procedure <CODE>MinDist</CODE> implements the constraint that the Hamming distance does not exceed the value of <CODE>Distance</CODE>. The list <CODE>Xs</CODE> holds the sets representing the single codes. The nested loop (<CODE>ForAllTail</CODE> and <CODE>ForAll</CODE>) imposes <CODE>MinDist</CODE> on all pairwise distinct elements of <CODE>Xs</CODE>. The distribution employs straightforwardly a naive strategy. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Hamming</SPAN> Bits Distance NumSymbols} <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">MinDist</SPAN> X Y} <BR> Common1s = {FS<SPAN class="keyword">.</SPAN>intersect X Y}<BR> Common0s = {FS<SPAN class="keyword">.</SPAN>complIn<BR> {FS<SPAN class="keyword">.</SPAN>union X Y}<BR> {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make [1<SPAN class="keyword">#</SPAN>Bits]}}<BR> <SPAN class="keyword">in</SPAN> <BR> Bits<SPAN class="keyword">-</SPAN>{FS<SPAN class="keyword">.</SPAN>card Common1s}<SPAN class="keyword">-</SPAN>{FS<SPAN class="keyword">.</SPAN>card Common0s}<SPAN class="keyword">>=:</SPAN>Distance<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Xs}<BR> Xs = {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>list<SPAN class="keyword">.</SPAN>upperBound NumSymbols [1<SPAN class="keyword">#</SPAN>Bits]}<BR> <BR> {ForAllTail Xs <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> X<SPAN class="keyword">|</SPAN>Y}<BR> {ForAll Y <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Z}<BR> {MinDist X Z}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {FS<SPAN class="keyword">.</SPAN>distribute naive Xs}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> </P><P> The following code generates a Hamming code for 16 symbols using 7 bit words and ensures a Hamming distance of 2. </P><BLOCKQUOTE class="code"><CODE>{Browse<BR> {Map {SearchOne {Hamming 7 2 16}}<SPAN class="keyword">.</SPAN>1<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> X} <BR> {ForThread 7 1 <SPAN class="keyword">~</SPAN>1 <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Is I} <BR> {FS<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>isIn I X}<SPAN class="keyword">|</SPAN>Is <BR> <SPAN class="keyword">end</SPAN> nil} <BR> <SPAN class="keyword">end</SPAN>}}</CODE></BLOCKQUOTE><P> Further, the code is nicely formatted displayed in the Oz Browser. </P><DIV align="center"><IMG alt="" src="hamming_browser.gif" id="hamming_browser.pic"></DIV><P> </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node2.html#fset.examples.steiner"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node4.html#fset.examples.binpacking">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|