A

p

e

r

s

o

n

a

l

B

l

o

g

Vegane Rezepte 2018

Recipes

Ich habe angefangen möglichst viele Rezepte zu Dokumentieren und in meiner Rezepte-Datenbank zu speichern. Ist 2018 schon recht voll geworden ;-).

Zyklische Redundanzprüfung (Theorie)

Hier geht es um Vektorrechnung. Dazu habe ich ja schon hier und da etwas gehabt: Komplexe Zahlen, Polynome, Vektorintegral. Jetzt geht es um Bitvektoren. Also nehmen wir hier als Beispiel eine Zahlenfolge aus 4 Bit 1101. Mit 4 Bit können $ 2^{4} $ Zahlen/Zustände abgebildet werden (hier 16 Zahlen).

Diese Zahlenfolge $ v_i $ mit $ v_i \in {0,1} $ wird jetzt als Vektor in dezimalen Zahlen abgebildet. Also als Polynom $ f $ mit Definition von Addition und Multiplikation. Die Summe der Koeffizienten entspricht dem Wert der Bitfolge. Hier: $ 13 $.

\begin{equation}f(x) = \sum_{i = 0}^{i-1} v_i\cdot 2^i\cdot x^i = 8x^3 + 4x^2 + 1\end{equation}

$ f $ sind die Daten, die zwischen Sender und Empfänger ausgetauscht werden sollen.

Das Generatorpolynom $ g $ ist konstant und wird vom Sender verwendet um die Prüfsumme von den Daten abzuleiten. Der Empfänger benutzt das Polynom zu Fehlererkennung der empfangenen Daten.

\begin{equation}g(x) = x^3 + x^2 + x\quad\hbox{mit}\quad grad(g) \leq grad(f)\end{equation}

Mit einem Trägerpolynom $ t(x) $ sollen Daten und Prüfsumme in einem Paket übertragen werden. Dazu werden Daten, die mit $ f $ abgebildet werden, durch Multiplikation mit $ x^{n} $ im oberen Bereich plaziert, im unteren Bereich ist Platz für die Prüfsumme der Daten, die durch addition angehängt wird. Die Prüfsumme hat maximal die Größe des Generatorpolynoms wodurch der Wert von $ n= grad(g) $ bestimmt ist.

\begin{equation}f^*(x) = (t\circ f)(x) = f(x)\cdot x^{n} = (8x^3 + 4x^2 + 1)\cdot x^3 = 8x^6 + 4x^5 + x^3\end{equation}

Wie die Prüfsumme gebildet wird und anschließend mit den Daten transportiert wird soll hier theoretisch disskutiert werden: Die Annahme ist, dass das Polynom $ f^* $ in einen ganzrationalen Anteil und einen echt gebrochenrationalen Anteil zerlegt werden kann:

\begin{equation}\label{eq:div} f^*(x) = q(x)\cdot g(x) + r(x)\quad\Leftrightarrow\quad\frac{f^*(x)}{g(x)} = q(x) + \frac{r(x)}{g(x)}\end{equation}

Es gilt dann zunächst $ grad(r) < grad(f) $. Durch iterierte Anwendung von \eqref{eq:div} kann der Rest immer wieder Zerlegt werden bis $ grad(r) < grad(g) $ gilt. Bekannt ist das Verfahren unter dem Namen: Polynomdivision.

\begin{equation}q(x)\cdot g(x) + r(x) = q(x)\cdot g(x) + (q_1(x)\cdot g(x) + r_1(x)) = ...\end{equation}

Der verbleibende Anteil $ r(x) $ mit $ grad(r) < grad(g) = n $ bildet die Prüfsumme. Der Träger $ t $ aus $ f^* $ und $ r $ wird durch Umformung aufgelöst:

\begin{equation}t(x) = f^*(x) - r(x) = f(x)\cdot x^n - r(x) = q(x)\cdot g(x)\end{equation}

Polynomdivision: Die Daten $ f^* $ werden durch das Generatorpolynom sukzessive geteilt. Das verbleibende Restpolynom bildet die Prüfsumme ab:

\begin{align}& 8x^6 + 4x^5 + x^3 : x^3 + x^2 + x= 8x^3 - 4x^2 + 9 \\ & -(8x^6 + 8x^5 + 8x^4) \nonumber\\ \hline & - 4x^5 - 8x^4 + x^3 \nonumber\\ & -(- 4x^5 - 4x^4 - 4x^3) \nonumber\\ \hline & -4x^4 + 5x^3 \nonumber\\ & -(- 4x^4 - 4x^3 - 4x^2) \nonumber\\ \hline & 9x^3 + 4x^2 \nonumber\\ & -(9x^3 + 9x^2 + 9x) \nonumber\\ \hline & - 5x^2 - 9x \nonumber\\\end{align}

Das Polynom aus Daten und Prüfsumme $ f^*(x) - r(x) $ hat entsprechend folgendes aussehen:

\begin{equation}t(x) = f(x)\cdot x^n - r(x) = 8x^6 + 4x^5 + x^3 + 5x^2 + 9x\end{equation}

Polynomdivision: Die Daten $ t $ werden übertragen. Das Polynom vom Empfänger erneut durch das Generatorpolynom $ g $ geteilt. Es sollte sich dann kein Rest mehr ergeben und die Übertragung war erfolgreich.

\begin{align}& 8x^6 + 4x^5 +x^3 + 5x^2 + 9x : x^3 + x^2 + x = 8x^3 - 4x^2 - 4x + 9 \\ & -(8x^6 + 8x^5 + 8x^4) \nonumber\\ \hline & - 4x^5 - 8x^4 + x^3 + 5x^2 + 9x \nonumber\\ & -(- 4x^5 - 4x^4 - 4x^3) \nonumber\\ \hline & - 4x^4 + 5x^3 + 5x^2 + 9x \nonumber\\ & -(- 4x^4 - 4x^3 - 4x^2) \nonumber\\ \hline & 9x^3 + 9x^2 + 9x \nonumber\\ & -(9x3 + 9x^2 + 9x) \nonumber\\ \hline & 0 \nonumber\\\end{align}

Um die eigentlichen Daten $ f $ aus dem Träger zu extrahieren, muss dieses durch das Polynom $ x^{n} $ mit $ n = grad(g) $ sukzessive geteilt werden:

\begin{equation}8x^6 + 4x^5 +x^3 + 5x^2 + 9x : x^3 = 8x^3 + 4x^2 + 1 + Rest\end{equation}

Der Rest ist in dem Fall uninteressant. Nur der ganzrationale Anteil spiegelt die Daten wieder.

Wie das Verfahren in der Praxis konkret aussieht, dann im Polynomring $ \mathbb{Z_2]}[x] $, wird hier nicht Thematisiert. Es vereinfacht sich aber einiges mit binären Operatoren. Es sei $ a,b,c\in\mathbb{Z_2}$ und $ x,y,z\in\mathbb{Z} $:

\begin{align}& a\hbox{ xor }b = c\quad\Leftrightarrow\qquad x + y \equiv z \mod 2\\ & a\hbox{ and }b = c\quad\Leftrightarrow\qquad x\cdot y \equiv z\mod 2 \nonumber\\\end{align}

Und macht das Verfahren dadurch praktikabel. Ein PDF vom MPI-INF hat eine Erklärung. Einen guten Einstieg bietet auch die Wikipedia.

Just my two cent

Just my two cent

Recently, I saw an example of how to solve a problem in different programming languages. The title was: “In Erlang, the Ruby code example would look like this”. Actually, I don’t know how the ruby code example looks like to solve the same problem, however from the point of what it does I can guess:

[-> a {a+10}, -> a {a*10}, -> a {a-5}].reduce(23) {|a, b| b.call a}

Right? No, Ruby is a fundamental object oriented programming language and the example would probably look different. But also, Ruby has some functional features. Like others:

Phython:    reduce(lambda x, y: y(x), [lambda a: a+10, lambda a: a*10, lambda a: a-5], 23)
Javascript: [a => a+10, a => a*10, a => a-5].reduce((a, i) => i(a), 23)
Haskell:    foldl (\x y -> y(x)) 23 [(+10), (*10), (+(-5))]
Racket:     (foldl (λ (b a) (b a)) 23 (list (λ (a) (+ a 10)) (λ (a) (* a 10)) (λ (a) (- a 5))))

List operations

Apply a function to each member of a list:

Ruby:       [1,2,3].map { |x| x * 2 }
Python:     map(lambda x: x * 2, [1,2,3])
Haskell:    map (*2) [1,2,3]
Javascript: [1,2,3,4].map(x => x * 2)
Racket:     (map (λ (x) (* x 2)) (list 1 2 3))

Flatten a list of multiple sublists:

Ruby;       [[1,2,3],[4,5,6],[7,8,9]].flatten
Python:     [item for list in [[1,2,3],[4,5,6],[7,8,9]] for item in list]
Haskell:    concat [[1,2,3],[4,5,6],[7,8,9]]
Javascript: [].concat(...[[1,2,3],[4,5,6],[7,8,9]])

Multiply all members of a list:

Ruby:       [1,2,3,4].reduce(1,:*)
Python:     reduce((lambda x, y: x * y), [1,2,3,4], 1)
Haskell:    foldl (*) 1 [1,2,3,4]
Javascript: [1,2,3,4].reduce((accu, item) => accu * item, 1)
Racket:     (foldl * 1 (list 1 2 3 4))

Filter all even members from a list:

Ruby:       [0,1,2,3,4,5,6,7,8,9].select &:even?
Python:     filter(lambda x: not x % 2, [0,1,2,3,4,5,6,7,8,9])
Haskell:    filter (even) [0,1,2,3,4,5,6,7,8,9]
Javascript: [0,1,2,3,4,5,6,7,8,9].filter(x => x % 2 == 0)
Racket:     (filter even? (list 0 1 2 3 4 5 6 7 8 9))

Sort a list ascending:

Ruby:       [5,9,0,1,3,2,4,8,6,7].sort
Python:     sorted([5,9,0,1,3,2,4,8,6,7])
Haskell:    Data.List.sort [5,9,0,1,3,2,4,8,6,7]
Javascript: [5,9,0,1,3,2,4,8,6,7].sort()
Racket:     (sort (list 5 9 0 1 3 2 4 8 6 7) <)

Element is member of the list:

Ruby:       [0,1,2,3,4,5,6,7,8,9].include? 5
Python:     5 in [0,1,2,3,4,5,6,7,8,9]
Haskell:    5 `elem` [0,1,2,3,4,5,6,7,8,9]
Javascript: [0,1,2,3,4,5,6,7,8,9].includes(5)
Racket:     (if [member 5 (list 0 1 2 3 4 5 6 7 8 9)] #t #f)

List of numbers between 100 and 200:

Ruby:       (100..200).to_a
Python:     range(100,200 + 1)
Haskell:    [100..200]
Javascript: Array(100 + 1).fill(100).map((e,i) => e + i)

Two lists and return a list of corresponding pairs:

Ruby:       [1,2,3,4,5].zip([5,4,3,2,1])
Python:     zip([1,2,3,4,5], [5,4,3,2,1])
Haskell:    zip [1,2,3,4,5] [5,4,3,2,1]

Minimum and Maximum of a list:

Ruby:       [:min, :max].map { |m| [5,2,6,2,1,7,3].method(m).call }
Python:     [m([5,2,6,2,1,7,3]) for m in [min, max]]
Haskell:    [m [5,2,6,2,1,7,3] | m <- [minimum, maximum]]
Javascript: [Math.min, Math.max].map(m => m.apply(null, [5,2,6,2,1,7,3]))
Racket:     (map (λ (f) (apply f (list 5 2 6 2 1 7 3))) (list min max))

Print each member of a list:

Ruby:       [1,2,3,4,5].each { |v| puts v }
Python:     print '\n'.join(str(p) for p in [1,2,3,4,5])
Haskell:    mapM_ (putStrLn . show) [1,2,3,4,5]
Javascript: [1,2,3,4,5].forEach(x => console.log(x))
Racket:     (map (λ (x) (println (number->string x))) (list 1 2 3 4 5))

Multiple lines to one single line string:

Ruby:       "Hello\nprograming\n world".lines.map(&:strip).join ' '
Python:     ' '.join([line.strip() for line in "Hello\nprograming\n world".splitlines()])
Haskell:    Data.Text.unpack $ Data.Text.unwords $ map(Data.Text.strip) $ Data.Text.lines $ Data.Text.pack "Hello\nprograming\n world"
Javascript: "Hello\nprograming\n world".split('\n').map(x => x.replace(' ', '')).join(' ')