ぼんさい塾

ぼんさいノートと補遺に関する素材や注釈です．ミスが多いので初稿から１週間を経た重要な修正のみ最終更新日を残しています．

Java のプログラム (23)

2011-12-11 18:04:55 | 暮らし
記事一覧
ソースコードについて


６．描画

6.1 JDK

アプレットの作成から始まる Java プログラミングの入門書と同様に

//------------------------------------------
//Fig.java
import java.applet.Applet;
import java.awt.Graphics;
public class Fig extends Applet {
    public void paint(Graphics g){
        g.drawLine(0, 0, 100, 100);
        g.drawOval(50, 50, 100, 100);
    }
}
//------------------------------------------

を JDK（Java Development Kit）でコンパイルして Fig.class を作れば

//-------------------------------------------------------
//Fig.html
<HTML><BODY>
    <applet height=200 width=200 code="Fig.class"></applet>
</BODY></HTML>
//-------------------------------------------------------

で簡単に直線と円を表示できます．

これに対して NetBeans の IDE で描画のアプリケーションを作ろうとして

  ファイル(F)＞新規プロジェクト(W)＞カテゴリ(C)：Java＞プロジェクト(P)：Javaクラスライブラリ＞次へ
  プロジェクト名(N)：chk2＞完了(F)

として chk2 プロジェクト に

  新規＞JAppletフォーム：JFig＞完了(F)

で JFig.java を作ると，自動生成されるソースコードはコメントを含めて 56 行です．また
 
  新規＞その他＞アプレットフォーム：Fig＞完了(F)

として Fig.java を作ったときに自動生成されるコードは 46 行です．このコードからコメントを削除し，
上記の JDK のときと同様に

  import java.awt.Graphics;

を加えて paint() をオーバーライドした Fig.java と実行結果を次に示します．
もちろん init() の処理を変更しなければ削除しても結果は変わりません．
なお，initComponents() は編集不能です．

//---------------------------------------------------------
import java.awt.Graphics;
public class Fig extends java.applet.Applet {
    public void init() {
        try {
            java.awt.EventQueue.invokeAndWait(new Runnable() {
                public void run() {
                    initComponents();
                }
            });
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
    private void initComponents() {
        setName("Form");
        setLayout(new java.awt.BorderLayout());
    }
    public void paint(Graphics g){
        g.drawLine(0, 0, 100, 100);
        g.drawOval(50, 50, 100, 100);
    }
}
//---------------------------------------------------------

    

自動生成されるコードを使わずにアプレットを作りたい場合，「java アプレット プログラミング入門」
の Google 検索で次のような資料が見つかります．

[5-11] アプレットプログラミング入門 - lecture.ecc.u-tokyo....
  http://lecture.ecc.u-tokyo.ac.jp/~cichiji/cp-05/cp-05-09-1.html
[5-12] Introduction to Java Programming/Javaプログラミング入門
  http://sp.cis.iwate-u.ac.jp/pub/java/
[5-13] Javaプログラミング入門
  http://www.ics.kagoshima-u.ac.jp/edu/taiken2002/MovingCircle.html
[5-14] はじめてのJava入門[Javaアプレット講座(サンプルプログラム)]
  http://www1.bbiq.jp/takeharu/Applet27.html
[5-15] 「JAVAアプレット プログラミング」
  http://omori.cside.com/java/java4.htm

描画に関する詳しい説明はこちら．

[5-16] AWTとSwingのペイント(paint)の仕組み
  http://homepage1.nifty.com/algafield/paint.html#swing_summary
  本稿は、AWTとSwingのペイントの仕組みを詳しく説明します。デベロッパのみなさんは、本稿を読んで、
  GUIを効率的に正しくペイント(paint)するコード（描画コード）を書けるようになってください。ただし
  本稿では、ペイントの仕組み（何がどこにいつ描画されるか--whereとwhen）を一般的に説明しますが、
  AWTやSwingの個々のAPIの使い方(how)には立ち入りません。上質なグラフィクスを作るためのハウツー
  は、Java 2DのWebサイトで入手してください。

巡回符号 (6)

2011-12-10 16:36:30 | 暮らし
sys.pdf
sys-s.pdf
sys.txt
記事一覧
               [4-32] ハミング距離

#45: 巡回符号

4 ビットのデータ a3a2a1a0 に対応する多項式 P(z) = a3z3 + a2z2 + a1z + a0 と多項式 G(z) = z3 + z + 1 の積を F(z) とします．この G(z) は z4 + 1 の因数なので zkF(z) mod (z4 + 1) も G(z) で割り切れます．したがって G(z) で割り切れる 6 次の多項式（係数は 7 個）の集合は巡回置換に対して不変となります．この集合が巡回符号です．個々の多項式（巡回符号の要素）を符号語，G(z) を生成多項式といいます．<--- 通常は z でなく x を使います（#33の両側 z 変換に記号を合わせただけ．解析接続は無関係．マネをしないこと）．

F(z) を送信したときに伝送誤りで F '(z) = F(z) + zp を受信したとすると F '(z) mod G(z) = zp mod G(z) ≠ 0 となり，伝送誤りが発生したことが分かります．また，符号多項式が 6 次で G(z) が原始多項式だから，単一誤りを仮定すると F '(z) mod G(z) （シンドローム）から誤りが発生した場所（ p の値）も分かるので誤りを訂正できます．

補足：（ブロック符号の場合は）符号語間のハミング距離でその符号の誤り検出・訂正能力を評価できます．巡回符号では生成多項式の次数を高くするとハミング距離の最小値が増加し，複数箇所の誤りも訂正できるようになりますが処理は面倒です．一方，誤りの検出は容易なので，誤った場合は再送を要求する方式も広く用いられています [4-41]．

[4-28] 巡回符号 - Wikipedia
 http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E7%AC%A6%E5%8F%B7
[4-32] ハミング距離 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2
  等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。
[4-33] ハミング符号 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E7%AC%A6%E5%8F%B7
  知られている誤り訂正符号の中では最も古く、ブロックあたり1ビットの誤りを訂正できる。
------------------------------
[4-34] 線型符号 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E7%AC%A6%E5%8F%B7
  符号化と復号が効率的
[4-35] 符号理論 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E7%90%86%E8%AB%96
[4-36] 誤り検出訂正 - Wikipedia
  http://ja.wikipedia.org/wiki/%E8%AA%A4%E3%82%8A%E6%A4%9C%E5%87%BA%E8%A8%82%E6%AD%A3
[4-37] ハミング限界 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E9%99%90%E7%95%8C
[4-38] ギルバート＝バルシャモフ限界 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%82%AE%E3%83%AB%E3%83%90%E3%83%BC%E3%83%88-%E3%83%90%E3%83%AB%E3%82%B7%E3%83%A3%E3%83%A2%E3%83%95%E9%99%90%E7%95%8C
[4-39] プロトキン限界 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AD%E3%83%88%E3%82%AD%E3%83%B3%E9%99%90%E7%95%8C
[4-40] リード・ソロモン符号 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%BD%E3%83%AD%E3%83%A2%E3%83%B3%E7%AC%A6%E5%8F%B7
  訂正能力が高く様々なディジタル機器等で応用されている。
[4-41] 巡回冗長検査 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB
  CRC-32-IEEE 802.3 は1975年に登場し、イーサネットなどの各種通信やZIPやPNGなど各所に使われている。
[4-42] 畳み込み符号 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E7%AC%A6%E5%8F%B7
  デジタルラジオ、携帯電話、人工衛星リンク、Bluetooth などの実装について、性能を向上させるためによく使われる。
[4-43] ターボ符号 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%BC%E3%83%9C%E7%AC%A6%E5%8F%B7
  宇宙探査機での通信など、ノイズのある限られた帯域幅で情報転送量を可能な限り最大化したい場合に使われている。
[4-44] 誤り訂正符号
  http://www.ohtsuki.ics.keio.ac.jp/pdf/class.pdf
[4-45] 同期方式 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%90%8C%E6%9C%9F%E6%96%B9%E5%BC%8F


巡回符号 (5)

2011-12-09 17:17:04 | 暮らし
sys.pdf
sys-s.pdf
sys.txt
記事一覧
                       [4-26] Ｍ系列の自己相関

#44: Ｍ系列

GF(2)上の多項式 x4 を原始多項式 x4 + x + 1 で割った有理式を級数に展開すると

     x4 / (x4 + x + 1) = 1 + x-3 + x-4 + x-6 + x-8 + x-9 + x-10 + x-11 + x-15 + ………

となり，右辺の級数の係数は長さ 24 - 1 = 15 の系列 100110101111000 の繰返しになります．この系列をＭ系列といいます．0, 1 を -1, 1 で置換したときの自己相関は上図のようになり（上図は n = 7），ランダム雑音に近いので擬似乱数として用いられています．

     x4 / (x4 + x + 1) = 1 / (1 + x-3 + x-4)

ですから，このＭ系列が循環する信号を， GF(2) 上の伝達関数が 1 / (1 + z-3 + z-4) である回路のインパルス応答とみることができます．巡回符号では符号多項式を考えるので，対応するｚ変換は両側ｚ変換になりますが，sys.pdf では因果的なインパルス応答をもつ回路で考えます（信号は多項式でもよい）．このＭ系列の１周期（のモニック多項式表示）を P(z) = z14 + z11 + …… + z3 とおくと

     1 / (1 + z-3 + z-4) = z-14 P(z) / (1 + z-15) = z-14 Σk P(z) z-15k

です．また，伝達関数  1 / (1 + z-3 + z-4) の回路に伝達関数 (1 + z-15) の回路を接続すると z-14 P(z) をインパルス応答とする回路になります．

補足：上記の級数の連続する４個の係数は計算途中の剰余もどき（線形帰還シフトレジスタの状態）を表しています．剰余もときが 0001 になった時点で循環が始まります． 100110101111000 を１ビットずつずらした４ビットのパターンに 0000 以外のすべてが含まれていることを確認してください．もちろん４ビットのパターンが表わす GF(216) の元の四則演算は原始多項式 x4 + x + 1 を法とする多項式の演算です．

[4-25] M系列 - Wikipedia
  http://ja.wikipedia.org/wiki/M%E7%B3%BB%E5%88%97
  重要な応用として擬似乱数列の生成がある。
[4-26] M-series generator polynomials
  http://www.finetune.jp/~lyuka/technote/lfsr/lfsr.html
[4-27] M系列信号の性質と応用
  http://www.cqpub.co.jp/dwm/contents/0007/dwm000701150.pdf


巡回符号 (4)

2011-12-08 23:37:55 | 暮らし
sys.pdf
sys-s.pdf
sys.txt
記事一覧
                             [4-24] 除算回路（p.33）

#43: 除算回路

「除算回路 有限体」や類似の語句で検索しても Web 上には有限体上の乗除算回路の分かり易い説明があまり見つかりませんでした．[4-22] は絶版になっている参考書です．Web 上の資料としては [4-24] があります．最近は汎用のプロセッサで処理するので，回路構成の知識は不要なのでしょう．信号を切り換えるスイッチの動作の説明が煩わしいので sys.pdf でも項目を変更するかも知れません．いきなり M 系列ではなく，つなぎの説明を考えます．

補足： 分数を有限長の小数で表わせないときは必ず循環小数になっています．このことを  100÷7＝14.2857142857142857… の場合で考えましょう．7 で割った剰余は 0, 1, …, 6 のいずれかですから，割り切れなければ 6 回目以内に同じ剰余が現れるはずです．GF(2)上の n 次の多項式で割ったときも同様に，0 でない剰余は 2n - 1 とおりしかないので 2n - 1 回目以内に同じ剰余が現れます．2n - 1 とおりのすべての剰余が現れるのが原始多項式で割ったときです．どのような多項式が原始多項式か感嘆には分からないので表で示されています．


[4-22] 符号理論（宮川，岩垂，今井）
  http://www.amazon.co.jp/%E7%AC%A6%E5%8F%B7%E7%90%86%E8%AB%96-%E5%90%8D%E8%91%97%E5%BE%A9%E5%88%BB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA%E2%80%95%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E5%9F%BA%E7%A4%8E%E8%AC%9B%E5%BA%A7-%E5%AE%AE%E5%B7%9D-%E6%B4%8B/dp/4885521807
  http://www.amazon.co.jp/gp/offer-listing/4885521807/ref=dp_olp_used?ie=UTF8&condition=used
[4-23] 線形帰還シフトレジスタ - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF
[4-24] 情報理論（2011-No.10）
  http://homepage3.nifty.com/yohara/LN2011/20111203-IT10.pdf
  12.36 巡回符号の符号化回路; 12.37 巡回ハミング符号の復号器


Java のプログラム (番外)

2011-12-07 22:01:10 | 暮らし

「Java のプログラム (22)」で作成したアプレットは HTML ファイル内に

    

のように埋め込んで使いますが，アクティブ コンテンツの実行を禁止しているサーバも少なくありません．
ここ は実行可能です．

演習問題：
(1) 計算結果だけを表示し，これを使った計算の入力を簡単化する．
(2) 整数の演算を実数の演算に変える．
(3) Math クラスをインポートして sin や cos の計算もできるようにする．
(4) メモリ機能を追加する．